Demystifying the Optimal Performance of Multi-Class Classification
Authors: Minoh Jeong
Martina Cardone
Alex Dytso
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayes error
estimation
classification
minimum error probability

Abstract: Classification is a fundamental task in science and engineering on which machine learning methods have shown outstanding performances. However, it is challenging to determine whether such methods have achieved the Bayes error rate, that is, the lowest error rate attained by any classifier. This is mainly due to the fact that the Bayes error rate is not known in general and hence, effectively estimating it is paramount. Inspired by the work by Ishida et al. (2023), we propose an estimator for the Bayes error rate of supervised multi-class classification problems. We analyze several theoretical aspects of such estimator, including its consistency, unbiasedness, convergence rate, variance, and robustness. We also propose a denoising method that reduces the noise that potentially corrupts the data labels, and we improve the robustness of the proposed estimator to outliers by incorporating the median-of-means estimator. Our analysis demonstrates the consistency, asymptotic unbiasedness, convergence rate, and robustness of the proposed estimators. Finally, we validate the effectiveness of our theoretical results via experiments both on synthetic data under various noise settings and on real data.

Demystifying the Optimal Performance of Multi-Class Classification
Minoh Jeong
Martina Cardone
Electrical and Computer Engineering
Electrical and Computer Engineering
University of Minnesota Minneapolis, MN 55455
University of Minnesota Minneapolis, MN 55455
Grong316@umn.. edu
mcardone@umn. edu
Alex Dytso
Qualcomm Flarion Technology. Inc. Bridgewater. 08807 odytso28gmail.co com
Abstract
Classification a fundamental task science and engineering on which machine learning methods have shown outstanding performances. However, it is challenging to determine whether such methods have achieved the Bayes error rate, that is, the lowest error rate attained by any classifier. This is mainly due the fact that the Bayes error rate is not known in general and hence, effectively estimating it is paramount. Inspired by the work by Ishida et al. (2023), we propose estimator for the Bayes етгог rate of supervised multi-class classification problems. We analyze several theoretical aspects of such estimator, including its consistency, unbiasedness, convergence rate, variance, and robustness. We also propose a denoising method that reduces the noise that potentially corrupts the data labels, and we improve the robustness of the proposed estimator to outliers by incorporating the median-of-in -fllaan----maan- -e-ns estimator. Our analysis demonstrates the consistency, asymptotic unbiasedness, convergence rate, and robustness of the proposed estimators. Finally, we validate the effectiveness our theoretical results via experiments both on synthetic data under various noise settings and on real data.
Introduction
Supervised classification problems are typical tasks in various fields of science and engineering, such machine learning, statistical signal processing, estimation, and detection. In supervised classification, a dataset consisting of several input feature-label pairs given. The goal of supervised classification task is to design effective classifiers, by leveraging the given dataset, to suitably label future input features, or equivalently, to classify future input features into one of the classes.
As the dataset is the only available resource the data distribution, the performance of a classifier typically measured by empirical misclassification rate on the test dataset (which subset of the given dataset). The best performance of existing classifier, that is, the so-called state-of-th of-he- new guarantees that the SOTA performance is close the theoretical
art (SOTA) performance, tends to be the point reference to measure the improvement classifier. However, there minimum misclassification rate, namely the Bayes eтrоr rate (BER). Thus, comparing the empirical misclassification rate with the SOTA error rate provides only relative improvement.
Having the knowledge of the BER essential in theory and practice. The BER indeed provides fundamental limit on the misclassification rate, which is critical for designing nigh-performing
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

classifiers. Moreover, one can leverage the BER to assess how good the SOTA performance is with respect to the theoretically optimal error rate. If the SOTA performance is nearly close to the BER, we can avoid wasting time and effort in designing new classifier. Furthermore, the BER indicates the inherent hardness of task and hence, can be seen as a benchmark for comparing the hardness of different tasks [13 46 83 Knowing the BER also brings the opportunity to detect whether test dataset overfitting occurs (which has sporadically happened [3 51 [5 II)): this overfitting can be detected since the BER provides the minimum misclassification rate and hence, no classifier will perform strictly better than it. We refer an interested reader to Appendix A for a thorough literature overview methods to estimate and bound the BER.
In this paper, we investigate the problem of estimating the BER of an M-class classification task directly from a dataset, where M 2 2 is arbitrary. Our technique to estimate the BER is different from a plug-in approach that first estimates the distribution from which the data drawn, and then evaluates the BER. Indeed, our BER estimators, which are proved to be unbiased, consistent and robust to label noise and outliers, do not require the estimation of the data probability density to perform an effective BER estimation. We start by assuming that the data labels are soft and real-valued, approximating the posterior probability of the class. We then relax this assumption on the data labels, and show the applicability of our estimators one-hot labels and other noisy datasets.
Contributions. Our contribution is summarized as follows. Inspired by [46), in Section 3 we first propose BER estimator for the case of soft data labels, and we show that it benefits from several
appealing properties, c.g., it is consistent, unbiased and asymptotically normal. In Section 3 we also propose a methodology. inspired by the median-of-men robust. Then, in Section 4 we study the performance of the proposed estimators in scenarios where the soft labels are corrupted by two typical types of noise, i.e., the case of noise that permutes/shuffles the labels, and the case of additive noise. For the first type of noise, our estimators have similar properties as in the noiseless case. However, for the additive noise case, our proposed estimators are not consistent. Because of this, we propose a denoising method that averages noisy labels associated with the same feature. The corresponding constructed estimator is shown be consistent. In Section 4 we also showcase that the noisy soft label framework can be used to study the case of one-hot labels, and we provide denoising method that encompasses the one proposed for the case of additive noise. In Section we validate the effectiveness of the proposed estimators via experiments both on synthetic data under various noise settings (e.g.. one-hot labels) and on real data using three different datasets, i.e., RIFAR-10H 4, -MNIST-H (46] and MovieLens (38). Finally, in Section we conclude the paper with some discussion on future research directions, which are worth further investigation.
estimator [63]. to make any BER estimator
Notation. Deterministic scalar quantities are denoted by lowercase letters, scalar random variables are denoted by uppercase letters, vectors are denoted by bold lowercase letters, and random vectors by bold uppercase letters (e.g., xr, X, x. X). We let x; (resp., (ax))) indicate the i-th value of (resp., æ&). ). Calligraphic letters X' denote sets, and | is the cardinality of X. 1 1{S) } is the indicator function that yields if S is true and 0 otherwise. [M] := (1,.... M). For E RM,, we let X be the i-th order statistics [18] of X, i.e., the i-th smallest value of X with i E [M]. Finally, I, is the
identity matrix of dimension and 4 (resp.. - denotes convergence (resp., equality) in distribution.
2 Problem formulation
We consider an M-class classification task in which an input feature æ is classified into a class := [M] Our goal is to estimate the minimum misclassification probability, that is the BER. E C==
In particular, we seek to estimate the BER based on a dataset D = {xx, y:) that follows an unknown data distribution, i.e., (.) S.i.d.
Px,y, where X E X' and Y E y C 1]
We assume that the label data y contains the information about the class c of the input feature x. implying that one can retrieve (z, c) from (x. When a classifier @ : X' - C employed for classification task, the corresponding misclassification probability is defined as E(Ø) := Pr( of C'), where C is the true class for X. The minimum value of this misclassification probability the so-called BER, denoted by Pa. which is formally defined next.
We assume that X' is finite set, but several of our results easily extend to the case when X' is an infinite

---

Definition 1 (Bayes error rate [50). Consider an M-class classification problem, where an input feature X has to be classified into class C [M]] The BER defined as
Pe inf { = inf E 1 { X) * C)), &E
Φ
where & is the set of all measurable functions ø X C. and the expectation taken over Px,c-
The misclassification probability {() depends on the quality of the classifier & and the BER is obtained by choosing an optimal classifier. In fact, an optimal classifier theoretically equivalent to the Maximum Posteriori (MAP) classifier [50), that is, ΦMAP (x) arg maxkec Pr(C k|X z). Plugging the MAP classifier into (T). the BER can written as
P. = E
max Pr(C k/Xx REC
where the expectation is taken with respect Px. Note that Pe E --1-
Our main objective to effectively estimate the BER from the dataset D. the remaining of the paper, we let v D + [0, 1] denote the estimator of the BER.
3 BER estimation with soft labels
Soft labels have several favorable properties (e.g., they help to prevent an overfitting problem, they lead to well-structured model, and they improve the prediction performance) that make them widely used in machine learning. For example, they are essential in label smoothing and knowledge distillation, which widely applied methods to improve model performance [8] 101)
There exist several types soft labels and here we assume that label soft represents the posterior probability. Specifically, say that D { y:) ) is dataset with soft labels if 2; E X and y; E y are such that
Pr(C 1 1 x; Pr(C = 2 = x,)
(3)
Pr(C = M|X xx:
This is a standard and widely adopted assumption; has indeed been argued 17 that using soft labels to approximate posterior probabilities enhances model performance. Definition 2 (Base BER estimator). The BER estimator t/soft (D) is defined as
35
42
61
69
101
sooft (D)
Σ (m.
(1
1
max Uj
JE[M]
We will use the base estimator usant in (4) building block for robust BER estimation. We note
that Veoft in (4) with M = retrieves the estimator proposed in [46). The next theorem (proof in Appendix B.I) provides three important properties of tisof. in (4)
Theorem 1. Assume that D contains soft labels as defined in Then, &aoot (D) satisfies the following properties:
1. (Unbiasedness): ([)soo(()) = Pe, that is, tholt (D) is an unbiased estimator of the BER:
(1-22) 22 In 5 with
2. (Consistency): For any 8 E 1), it holds that |p - Pel V
2n
probability at least 1 - 5, that is, Mesott (D) is consistent estimator of the BER;
3. (Asymptotic Normality): Vn(wbso P.) $ No0 Var(YM:MM) as + oc.
Theorem [soows that the BER can be effectively estimated directly from dataset that contains soft labels as in (3). Moreover, highlights that the convergence rate of slo (D) is n. 2 which is indeed the optimal (parametric) convergence rate.
3

---

Another important aspect to assess the performance of Usoft (D) is to measure how far it is from the BER P.. Since sonn (D) is unbiased (from Theorem this distance can be measured by computing the variance of Ssaft (D), which is denoted as Var(Wsoft) and provided by the next proposition (proof in Appendix B..2p.
Proposition 1. It holds that Var(Wsntt)) = 1, Var(( (YM:)) and Var((sant) (1- P.
4n
The exact computation of (ar()))))) ) in Proposition ! requires the knowledge of the order statistics of Y and hence, of the label distribution Py. The upper bounds on Var(tsoft) are instead distribution- independent. In particular, both upper bounds show that the rate of convergence of Var (soo))
1/n, which is in line with Theorem [ Moreover, the first upper bound on Var( implies that Var(W + O when either P. - 0 (i.e., also known as realizability assumption (76]) or Po 1 M (i.e., labels and features are independent). The first upper bound on Var(tisot) also
allows to find an upper bound on P. which becomes tight when Pe - 1 - 1/M.
3.1 Robustness of vlsoft
We consider robustness to outliers, where an outlier is data sample that is corrupted by high noise. We use the concept of breakdown point [44] [60] to measure the robustness of Vantt The breakdown point captures how robust estimator with respect to outliers 2 In the classical definition of breakdown point, the worst estimator (in terms of robustness) for a dataset 'D with outliers is defined as (D) = co. However, in our setting teooft (D) 1 1 since s/oott (D) is estimate of P.- Because of this, we next adopt an alternative definition for the breakdown point which is commonly used for bounded parameter space θ (45).
Definition 3 (Breakdown point). Consider an estimator 3b : Q" + θ of 0 E e S RR. Let D(*) = (D..... DuJ. where D; E 22 Vi E [k]]. be a clean dataset without outliers, and let D(r) = (D.... } be a noisy dataset that is composed of 7 noisy data samples that can be
arbitrarily replaced by outliers. Then, the breakdown point of &b is defined as
B(w)=
min ST
sup (D(((()))) (D(())) (k) U ((T))) > ||aa(()]]
(5)
(K+T
where the sup is taken over all D(x+r), D(()) and D(rr such that D(.) C D(n+t), and re) is the vector consisting of the L radii of the largest L-dimensional ellipsoid in θ
B(b) in (5) quantifies the value of the breakdown point for an estimator e + + θ In particular, an estimator vi "breaks down" if (D((+T)) changes of at least ||rad when r clean data samples are replaced with T outliers. The breakdown point is defined as the minimum ratio between the number of outliers (T) and the total number of data samples (x + 7), such that 7 outliers are sufficient to break the estimator (D(++7)) From Definition 3 it is clear that the higher the value of the breakdown point, the more robust the estimator is. To measure the breakdown point of e'soft we start by noting that tsoft is the sample mean of {1 (8x (see (4)). Thus, using the notation as in Definition 3 we have that θ = [o, 1 which leads to re = 1/4 - 2M
1 This
implies that B (Vooott) = (e.g., when D contains an outlier y such that max]e[M] Vj = oo) and hence, Wio is not robust outliers.
We next propose a methodology, inspired by the median-of- estimator 65 to make any BER estimator (and hence, also thson)) robust.
Definition 4 (Median-of-BERR (MoB) estimator). Consider any BER estimator & and a dataset D. First, partition D into K sub-datasets DA, k E [K] such that [D] = = cK, where e E N is the number of data samples in Dx. Then, the Median-of BERf (MoB) estimator defined as
MoBx (1b, D) med (Dx( ) k e [K]}),
where SS) is the sample median of S.
"The sample mean can fail to estimate the true mean by a single outlier (e-g.. sample x with a value very different from the true mean). Thus, the sample mean has a breakdown point equal to 1/n, meaning that one outlier can break the estimate. Differently, the median is more robust since it has a breakdown point of 1/2, i.c., half of the samples need be outlirs for breaking the estimate.
Any L-dimensional ellipsoid (after rotation) can be defined as + are 01, 02 .... OL.
1. Then, the radii

---

The next theorem (proof in Appendix B.3 provides three important properties of MoB (1/oott D).
Theorem 2. Assume that 'D contains soft labels as defined in Then, the MoB estimator MoBx (Paott: D) satisfies the following properties:
1. (Consistency): For all t S K, with probability at least 4E 2t, holds that
[MBB (Wsoft, D) Pals 2 2V33ar((M..)) vn-K +3v (VVear(YMM)))
(1 M)
K
n- (7)
and hence, MoB MoBx(1eoft D) a consistent estimator of the BER:
2. (Breakdown): Its breakdown point is given by B (MoBx(Waoft: D)) = K+1 1. n
3. (Asymptotic Normality): If K 7 oo and K dvn) n
then
v (MoBx (P/oot, D) Pc) 4 N (0, Vor(YMaa)))
Theorem shows that MoBx D) has the same rate of convergence of as soft (see Theorem However, MoBx [ioottt D) has higher breakdown point (and hence, is more robust) than s/ Nonetheless, this robustness attained at two expenses: (i) MoB (loBx(Wssan) (N/sott D) is not an unbiased estimator of Pe; and (ii) the variance of MoB y a factor of //2 in the asymptotic regime.
(/ (N/ooit D) is larger than the one of thoft by
Theorem 2 also points out to an interesting trade-off, with respect to K, between accuracy and robustness. For example, setting K v leads to higher breakdown point (and hence, is more robust) than setting K = In However, the concentration bound in ( (which measures the accuracy of the estimation) has a much larger value with K /n than with K Inn.
4 BER estimation with noisy labels
The soft label data discussed in Section B might be challenging to obtain as data labels are often corrupted by noise or other perturbations. In such scenarios, data labels are unreliable (27 64 68
and several studies have been conducted on them 37
57
80
88
90
92
94 96
With the goal to broaden the applicability of v/soft (or its robust version MoB (thsoft: D)), here study their performance in scenarios where the soft labels are corrupted by various typical types of noise
We denote by Y ~ P the noisy soft label, i.e., noisy soft label Y D is distributed according to the conditional probability distribution Pv where y, is the true soft label.
4.1 Additive noise on the data labels
We here consider the case where the labels corrupted by additive noise, i.e., have (x,, ÿ) DA where ÿ = y + z, where z is an M M-dimensional random noise vector. We assume that z has i.i.d. components each with zero mean.
We start analysis by showing that v'soft in 4 applied on D is neither a consistent nor an unbiased estimator of Pa. We, in fact, have that
Peo (DA)= =
max (B:)) + (z:),). jE[M
(8)
which, by the law of large numbers, converges to
lim csoot (DA) 1- - 20030
max (Y, + 2,) JE(M]
(9)
Then, the inequalities max; v, + ming D/ 5 maxx (x: + vi < max; v; + max, Yj imply that
E ZI.M] < P.
lim v/soft (DA) S E[ =+000
(10)
We refer interested reader Appendix B.4 where noise that randomly shuffles the labels is also studied.
5

---

which follow from and (3. The bounds in (TO) demonstrate that with labels corrupted by additive noise, Usoo is (in general) an inconsistent estimator of P.. By following similar steps, can be easily proved that whoftt is also a biased estimator of P.. In particular, the bounds in (TOp show that s/soft has a bias which is bounded by the expected value of the smallest (lower bound) and of the largest (upper bound) order statistics of the noise. In what follows, we provide two examples of distributions for which bounds on these expected values have been computed.
Example 1. Let Z i.idd
Uniform(-au a). Then, B[Zea]]
which + oc implies that M+I
2ni
IPe -sottt (Dx) S
M-1
M+11
Example 2. Let Z i.dd.
Then, we have that BiZM.M] -BBlZ and 9 which as n implies that IP Usoo (Da) /2 In M.
2-suu-Gauusiin
M S V 27 In M
Our analysis above shows that vh (DA) is (in general) an inconsistent and biased estimator of Pe- Because of this, we next propose a new BER estimator, which (different from thson)) leverages the features (ar, ji=1 denoise V, We refer to this estimator 1/DN. Our main intuition behind proposing DDN stems from the fact that data samples having the same feature æ should be labeled with the same (or at least similar) label. This can be attained by noting that, even if labels are noisy, is possible to minimize the effect of zero-mean noise by averaging the noisy labels associated with the same feature. We next formally define our denoising BER estimator VDDN IRM + [0, 1].
Definition 5 (Denoise estimator). For noisy dataset D s(x;)) for all i E [n], be defined as
{ W.) let the denoised label
8 sxx;) = Σ 1x, x; 1,
(1I)
2ド=1 1(23 = mi)
and let idx(x;)) = arg max (s{>)))) Then, the denoise BER estimator is defined as
a
VDN (DA)
Σ (1
(12)
n
The next theorem (proof in Appendix B.5 provides some important properties of 1/TNN (Dx).
Theorem 3. Let DA- = ((x 9=) be dataset that consists of noisy soft labels Y; = y: + z;
where zi s.d.d. Pz is the zero mean noise. Then, VDN (Dx) is consistent estimator of P.- Moreover, the noise has bounded support, that Pr(Z E [a, 6) = 1, then
1. (Asymptotical unbiasedness): (DA) is asymptotically unbiased estimator of Pe:
(1 t -a+b)² In 3
2. (Denoising Consistency): For any 8 E (0, 1), it holds that [s(x)- ((x))-y yyl < V
2n
with probability at least - 8, where ne = Σ}=1 1(x, = x}} and s(x) is the denoised label defined
The results in Theorem broadens the applicability of an effective BER estimator a larger class of datasets, e.g., to scenarios where the dataset includes multiple data samples representing the same feature. For example, V'DN works well on a noisy dataset where each data sample has multiple labels.
Moreover, as we will see in Section 4.2 dDDN is also useful for one-hot labels. We also expect that d'DN will work well with privatized datasets where noise was added to enhance privacy (26].
Remark Our estimator VDN only requires the dataset DA. This is more practical approach than the one in [46] which instead also requires the true one-hot label. The estimator in [46), which is referred to as genie estimator Vgenie. can be obtained by replacing s(x) in (II) with the true one-hot
label. In Appendix B.6. we provide properties of Mgenie (DA) that generalize the results in [46] for
any M 2. As expected, v'genie is a consistent and unbiased estimator of P..
x242 ..--su--Guussss Gaussian if MZ- Se V.ER.
We say that random variable Z is -sub

---

4.2 One-hot labels
dataset consisting of one-hot labels, denoted as (a,, V. -=) contains little information about the class posterior probability. We assume that the one-hot label is constructed from the corresponding soft label as follows,
Y = c; with probability Y;:
(13)
where: (i) Y the one-hot random vector; (ii) Y the soft label random vector in (3); and (iii) e, E Rd is the standard basis vector with one in the i-th position and zero in all the other entries.
We can think of the one-hot label construction in (13) as noisy label. Specifically, the noise E {ee - y with the probability mass function PZ (zly) = Σه 1 - e; - y satisfies and hence, denoise estimator LDD (DA) [12 or its robust version MoB (WDN. DA), can estimate the BER also for the case of one-hot labels. However, we also note that with the above construction, the labels might be too noisy estimate the BER practice. This suggests that a more refined denoising method than the one in Definition 5 for one-hot labels might be needed for more effective BER estimation.
= Y Z. It not difficult to see that = -
Motivated by the above diseussion, leverages neighbor samples to mitigate the noise Tuise[OOu Our choice of such denoising method mainly stems from the fact that one would expect that neighboring samples should have similar posterior probabilities. In particular, for each 2;, E [rl], we consider all of its neighbors (features that are at most a distance from 2;)) and we average the corresponding noisy labels We next formally define our denoising BER estimator, which we refer to as VC.
propose denoising method for one-hot labels, which
spirit similar to (II).
Definition 6 (Cluster denoise estimator). Given d X² - R. and E IR,, define Cluster; = {(x, y) E DA d(æ;, a)) S r). Then, the denoised label for U.. for all i E [m.]. is defined as
(14)
Clusterr|
and the cluster-based BER estimator is defined as
the (D( Σ
(1-
(I- max (0.),}) JE[M]
(15)
Remark 2. Preprocessing the dataset that aggregates data samples of similar features can also be helpful improving the BER estimate for noisy labels, and can be paired with the cluster denoise estimator in Definition 6 A naive approach would consist of reducing the feature dimensionality and increasing the number of data samples inside clusters (4). which helps mitigate the effect of the noise. Some notable examples of data preprocessing are the classical principal component analysis (PCA) (77) and the representation learning (5) (c.g., variational auto encoder (52)).
Remark 3. Another viewpoint to the denoising method in (14) is the connection to the non-parametric
estimation of the conditional expectation Y x). where Y is the true soft label corresponding
to X = x. In particular, estimating E Y x) is equivalent to denoising the noisy label associated
with as in [4. Under such a viewpoint, the BER estimator in Definition 6 resembles the
Malaraya-Watson estimator with Parzen window kernel 63 89
5 Experiments
We empirically validate our results using various datasets, namely: 1) synthetic dataset with different noises, including one-hot labels; 2) two benchmark datasets CIFAR- 10H (4] and Fashion-MNIST. [46]; and 3) Movielens [38], a real-world dataset for movie recommendations We compare our estimators with two SOTA BER bounds [72), namely the generalized Henze-Penros (GHP) BER bounds (75] and the k-Nearest Neighbor (NN) BER bounds [16]. Details on the k-NN bounds and
GHP bounds, and additional results can be found in Appendix C
Several works have taken advantage of neighbor samples to estimate the BER or the probability divergence. We refer interested reader (77 and references therein.
7

---

0.6
0.0
0.4
0033
-02
class
dlsse
dlass
-0.1
Figure I: 4-classes Gaussian data samples. The left figure shows the samples of each class, and the right figure displays the corresponding soft label information as the maximum value of the soft label.
BER
J-NN upper bound
GHP upper bound
(oR,((h))
GHP Lower bound
I-N lower bound
16
0.6
6.44
0.20
0.50
11:35
3.00
1,25
1.50
1.73
2.00
01333
0.30
0.75
1.00
3.25
1.50
1.70
2.00
0.30
1022
0.10
[BE2
0.00
0.20
0.25
0.50
0.70
1.50
1.20
1.50
1.75
2.00
0.25
0.30
0.70
1.00
1.20
1.50
1.70
2.00
(a) Soft labels.
(b) Noisy soft labels.
Figure 2: Comparison of MoBx where the is defined in (15) with the GHP bounds and the k-NN bounds with k 1. We consider 2, 000 samples generated in Figure | with noise ~~~ (0, 41.. MoB (t'c) uses K = Lvnj (with this choice, Theorem ensures the asymptotic normality of MoBx), ), the Euclidean distance for d, and r = 1/5.
Synthetic dataset with soft labels and noisy labels. We consider a 4-class classification problem with equiprobable classes C E C, == (), p), (-H, -w), (μ. -p)}, where >> 0 is parameter that controls the classification hardness. We generate the feature X E TR2 according to 2- 2-dimensional Gaussian distribution with mean (i.e., realization of C E Cp) and covariance matrix 12. The corresponding soft labels y, are then obtained by the Bayes' theorem. In particular, since fxic N(C, 12) and (c(c) 1/4 if C₁. (and zero otherwise). according (3) we have (xio(mmle))Pee)) that (y,)x Esec, fx (x.
Figure illustrates n 000 features (left figure), and the corresponding soft labels (right figure) for the synthetic dataset generated as explained above; in particular, for each feature 2;, we only reported the label (y,),- where j = arg max (yr); which is required for evaluating shoit in 4 As expected, point the decision boundary (lines for x; or 22 = 0) has a smaller maximum value in its soft label.
The results in Figure empirically demonstrate the effectiivnesss of our estimators, which consistently outperform the others Moreover, our estimators estimate the exact value of the BER, while the others derive upper and lower bounds on the BER, which might not be tight.
Without loss of generality, consider the following mapping: & 1 if (p.1): ks 2ifc (- 1t): 3 (-p. -p); and 4 iff (n, -w) 'Among the proposed estimators, in Figure we only evaluated MoB x (Vc) since we observed that it performs well with respect SOTA methods and hence, omitted the other estimators.

---

KoSychh)
60
0'2
BER MeBgiee
600
00
250
surpçhea
samplic
Pe-
(b) 1/ Pa and variance.
Figure 3: Comparison of Mo (Vc) (evaluated with thc in (55) with Usoft on noisy soft labels. We consider Z ~ .V (0, 1/554). To model outliers, we added Z 0.2 Ber (1/2) with probability 1/10 to each entry of the soft labels. For different n, the parameters of MoB x (1e) are chosen as K Lvnj, d is the Euclidean distance, and 1/5. We iterate the experiment 50 times for each n.
We further conducted experiments to verify the effectiveness of our denoising and robustifying methods data samples with label noise and outliers. Figure 3 shows the comparison of the denoising estimator MoBx x (Wc) with the base estimator s/soft We observe that sooft suffers from the label noise, which leads to bias in the estimation. However, suitably denoises the noisy labels and effectively estimates the BER. As shown in Figure 3b in fact, the absolute error between the estimate and the BER well as the variance decrease grows.
denoising estimator MoB g (vc)
Synthetic dataset with one-hot labels. We an- alyze the performance of MoB (#c) in the same Gaussian setting described above, but with one-hot labels. Each soft label of the samples is mapped to one-hot label according to the categorical dis- tribution with probabilities equal to the soft la- bels (see (33). Figure 4 shows that our denoising method capable of suitably reducing the noise in one-hot labels; in fact, it correctly estimates the BER after around 10 samples when MoB (Ne) converges to the BER. From Figure we also ob- serve that sof performs poorly; this suggests that denoising methods are essential for the BER esti- mation task, hence worth further investigation.
0.30
6.20
BER
6..0
MoByl0d
0.30
0.05
101
Number camplee
Figure 4: Comparison of MoB (Vc) with Vsof. for Gaussian samples with one-hot labels.
CIFAR-10H 4 and Fashion-MNIST-HH
46
The CIFAR-10H dataset variation CIFAR-10 constructed by labeling 10a images in the test dataset of CIFAR-10 by multiple labelers. The Fashion-MNISTA dataset is populated by 10* images in the test dataset of Fashion-MNIST (93 in a similar manner. These two datasets have 10 classes, but we further categorized these into M E (2, classes. In particular, for CIFAR-10H
we assigned C = (airplane, automobile, ship, truck), C2 = (bird, cat, deer, dog, frog, horse} when M 2, and C₁ fairplane, automobile, ship, truck). C2 {cat, dog, frog). C3 (bird, deer, horse) when M 3. Similarly, for Fashion- Miltion-MNISTHH.. we assigned C₁ = (t-shirt/top, pullover, dress, coat, shirt). C2
ftrouser, sandal, sneaker, bag, ankleboot] when M 2, and Ci (t-shirt toop, pullover, coat, shirt), C2 = (trouser, dress, bag), and C3 (sandal, sneaker, ankleboot) when M 3.
From Table 1 we observe that the estimates using MoB (VDDN) with K
|vn| are slightly lower g We also highlight that the
than VDNN which is due to the robustness of Mo to outliers BER estimates can leveraged to determine which task is more difficult. Intuitively, performing
"In general, there might be outliers that lead to low values of the estimated BER. However, since the labels belong to [0, 1] and the estimated BER values in our examples are very small, it is reasonable to assume that outliers with large values would be more impactful than outliers with small values.

---

Table 1: BER estimate on benchmark and real- world datasets.
CIFAR-IOH
Fashion-MNISTA.
MovieLens
classes
2
3
10
3
10
2
3
L/DN
0.0050
0.0177
0.0456
0.0348
0.0932
0.2825
0.3063
0.4031
MoBx (WDDN
0.0044
0.0168
0.0440
0.0347
0.0931
0.2816
0.3065
0.4035
the classification task over CIFAR-10H is much easier than performing it over Fashion-MNIST-HI and this is supported by the results in T i.e., the BERs associated with CIFAR-TOH are smaller than those over Fashion-MNIST-HH It is worth noting that test dataset overfitring can happen when benchmark datasets considered 3 46 51 59 91]. This can also be observed by the results in Table where our BER estimates of the 10-class classifications are larger than the SOTA error rates of 0.005 on CIFAR-10 by (24) and of 0.0309 on Fashion-MNISS by (82). We also suspect that, since the labels are assigned by humans, who might not be experts, the datasets might still have a considerable amount of label noise, which would lead to incorrect BER estimates. However, no estimators (including ours) can estimate the BER from a dataset that contains very noisy labels.
MovieLens [38]. This dataset consists of 25 million ratings to 62, 000 movies by 162, 000 users. Each rating ranges from 0.5 to 5 with step size 0.5. We first considered a movie classification task: a user either likes a movie or not. This is a complex binary classification task with the input feature being movie (in general, two-hour long video with audio) and the class being either O (dislike the movie) or 1 (like the movie). To ensure that a label belongs to [0, 1], we applied min max-max normalization each rating. Moreover, in order to have enough ratings for each movie when we applied the denoising method, we filtered out some data if the number of ratings was smaller than 100. Then, IDDN and MoB x (WDN) estimated the BER of such movie classification task, and they yielded a BER of around 0.3. We then categorized the ratings into M = 3 classes, i.e., we assigned C1 = (0.5, 1.0, 1.5), C2 = (2.0. ..... 3.5) and C3- (4.0, 4.5, 5.0). On this task, the BER estimate is around 0.4. These BERs are quite large, implying that the movie classification is a hard task to perform. This may be justified by the fact that ratings of movies are subjective, and movie recommendations are indeed challenging without users' information (e.g., content-based 47 or item- 74 recommendation systems use users' information).
Conclusion
In this paper, we investigated the challenge of estimating the BER for multi-class classifications. We proposed a BER estimator, v/soft, which we proved to be unbiased, consistent, and asymptotically normal when applied to soft-labeled datasets. By leveraging the median-of- -f--n method, we also proposed a methodology to make any BER estimate robust. To ensure the applicability of the BER estimator in practical scenarios, we analyzed the challenges posed by noisy soft labels, including those with additive noise and one-hot labels. For such noisy labeled datasets, we developed denoising techniques that effectively mitigate the label noise by using the corresponding features. We showed that these denoising BER estimators are unbiased and consistent under mild noise assumptions. Our experimental results, drawn from synthetic and real-worids datasets, validated our theoretical results.
Although in this work we assumed that the set of features is finite, several of our results (e.g.. Theorem
M and Theorem can be easily shown to hold also for the infinite feature space. A research direction worth further investigation would consist of proving that the cluster denoise estimator in Definition has similar appealing properties (see Theorem B) as the denoise estimator in Definition (which assumes that the set of the features is discrete). Always along these lines, a second interesting future work would be to analyze the rate of convergence of our BER estimator paired with the denoising method as a function of the characteristics (e.g., cardinality, distribution) of the feature space. Such an analysis would indeed provide insights into the difficulty of a classification task. Another relevant avenue for future research lies in assessing the optimal performance of multi- label learning, where a single data point can be associated with multiple classes. While adapting our framework to predict the minimum Hamming loss for multi-label learning might be relatively straightforward, estimating other metrics (e-g., the Fl score and the exact match ratio) might be a difficult task, potentially necessitating new methodologies.
6
10

---

References
[1] A. Antos, Devroye, and L. Gyorfi. Lower bounds for Bayes enror estimation. IEEE Transactions Pattern Analysis and Machine Intelligence. 21(7):643-6455 1999.
[2] H. Avi-Itzhak and T. Diep. Arbitrarily tight upper and lower bounds the Bayesian probability of error. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1):89-91, 1996.
[3] Barz and Denzler. we train test data? purging CIFAR of near-duplicates. Journal of Imaging. 6(6):11 2020.
[4] M. Battleday, J. C. Peterson, and Griffiths. Capturing human categorization of natural images by combining deep networks and cognitive models. Nature Communications, 11(1):5418, 2020. doi: 10. 1e..//0/3446--0000 020- 18946-2. URL https://dooi org/10 10. 1038/ 541467 020 18946-2
/
[5] Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(8):1798-188 1828, 2013, doi: 10.1109/ 203M0.
[6] V. Berisha. A. Wisler, A. O. Hero, and A. Spanias. Empirically estimable classification bounds based on a nonparametric divergence measure. IEEE Transactions on Signal Processing, 64(3):580-591, 2016. doi: 10. 1099TT992201
[7] Bhatia and Davis. A better bound on variance. The American Mathematical Monthly, 107(4)) 2000.
[8] D. Bockee and C. van der Lubbe. Some aspects of error bounds feature selection. Pattern Recognition, 3335-3333,,,0, 1979.
[9] Boucheron, G. Lugosi, and P. Massart, Concentration Inqqualities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[10] L. Buturović, Improving k-nearest neighbor density and error estimates. Pattern Recognition, 26(4): 611-616, 1993.
[11] C. Chen. Theoretical comparison of class of feature selection criteria in pattern recognition. IEEE Transactions Computers, C-20(9):1054 1056, 1971. doi: 1.711...999..22000
[12] C. H. Chen, On information and distance measures, error bounds, and feature selection. Information Sciences, 10(2):159-173, 1976.
[13] Q. Chen, Cao, Y. Xing, and J. Liang. Evaluating classification model against Bayes Transactions Pattern Analysis and Machine Intelligence, pages 1-16, 2023. doi: 10.1 109/TAM.P 2023.3240194.
IEEE
[14] Chernoff. measure asymptotic efficiency tests hypothesis based sum of observations. The Annals of Mathmmatcal Statistics, pages 493-507, 1952.
[15] M. Cover. Elements of Information Theory. John Wiley & Sons, 1999.
[16] M. Cover and P. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21 27, 1967. doi: 10. 10.1100/77.1196.100555
[17] Dao, G. Kamath, Syrgkanis, and L. Mackey, Knowledge distillation as semiparametric inference. In International Conference on Learning Representations, 2021. URL, httl:tttt////oeeerriiii .et. Forum?id==4UCFFN
[18] H.A. A. David and H. N. Nagaraja. Order Statistics. Wiley Online Library, 2004.
[19] P. A. Devijver. On a new class of bounds on Bayes risk in multihypothesis pattern recognition. IEEE Transactions on Computers, C-23(1)770880, 1974. doi: 10.1 10.1009T-C.197..2200
[20] P. A. Devijver and J. Kittler. Pattern Recognition. Prentice Hall, Old Tappan. NJ, July 1982.
[21] L. Devroye. On the asymptotic probability of error in nonparametric discrimination. The Annals of Statistics, (16):1300-1321 1981.
[22] L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Puttern Recognition, volume 31. Springer Science & Business Media, 2013.

---

[23] L. Doob. Regularity properties of certain families of chance variables. Transuctions of the American Mathematical Society, 47(3):455-486, 1940.
[24] A. Dosovitskiy, Beyer. A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani. M. Minderer. G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Representations, 2021. URL http::///pppppproeoooeeeeeeetrts
[25] O. Duda, P. E. Hart, al. Pattern Classification. John Wiley & Sons, 2006.
[26] C. Dwork. Differential privacy. In Automata, Languages and Programming; 33rd International Col- loquium, ICALP 2006, Venice, Italy, Jul 10-14, 2006, Proceedings, Part II 33, pages 1-12. Springer, 2006.
[27] Frenay M. Verleysen. Classification in the presence label noise: survey, IEEE Transactions on Neural Networks and Learning Systems, 25(5):845 869, 2014. doi: 10.1109/TNLLS.011 201.......011.2298889 2292894.
[28] J. H. Friedman and L. C. Rafsky. Multivariate generalizations of the wald-wolfowitz and smirnov two-sample tests. The Annals of Statistics, pages 697-717, 1979.
[29] K. Fukunaga. Introduction to Statistical Pattern Recognition (2nd Ed.). Academic Press Professional, Inc., USA, 1990. ISBN 0122698517.
[30] K. Fukunaga and L. Hostetler. k-nearest-nee mecrrest Bayes-risk estimation. IEEE Transactions on Informa- tion Theory, 21(3):885-29) 1975, doi: 10.1109/TT.1197.10055777
[31] K. Fukunaga D. M. Hummels. Bayes error estimation using Parzen k-NN procedures. IEEE Transactions on Pattern Anayssis and Machine Intelligence, (5y:63-643, 1987.
[32] K. Fukunaga and D. M. Hummels. Bias of nearest neighbor error estimates. IEEE Transactions on Pattern Analysis and Machine Intelligence, (1):103-112, 1987.
[33] K. Fukunaga and Kessell. Nouparametric Bayes error estimation using unclassified samples. IEEE Transactions on Information Theory, 19(4):334444, 1973. doi: 10.1 (09/TTT.1973 1055049.
[34] E. Garber and A. Djouadi, Bounds on the Bayes classification error based on pairwise risk functions. IEEF Transactions on Pattern Anolysis and Machine Intelligence, (02))221-288, 1988. doi: 10.1109/3.3891.
[35] Grossmann, L. Schmarje, and Koch. Beyond hard labels: investigating data label distributions. arXiv preprint arXiv:2207.06224 2022.
[36] L.-Z. Guo, Z.-Y. Zhang, Y. Jiang, Y.F. Li, and Z.-H. Zhou, Safe deep semi supervised learning for unseen-class unlabeled data. In International Conference on Machine Learning, pages 3897-3906. PMLR, 2020.
[37] Han, Q. Yao, X. Yu, G. Niu, M. Xu, W. Hu, I. Tsang, and Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in Neural Information Processing Systems, 31, 2018.
[38] F. M. Harper and J. A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst. 5(4), dec 2015. ISSN 2160-6455. doi: 10.1145/2827872. URL httph::////ooo httpp/////oiioorr///// org/10. 1145/ 2827872
[39] W. Hashlamoun, P. Varshney, and V. Samarasooriya. A tight upper bound on the Bayesian probability of error. IEEE Transactions Pattern Analysis and Machine Intelligence, 16(2):220 224,, 1994. doi: 10. 10.1109/34.273728.
[40] K. He, X. Zhang. S. Ren, and Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 770-778, 2016.
[41] M. Hellman and Raviv. Probability of error, equivocation, and the Chermoff bound. IEEE Transactions on Information Theory, 16(4):368-33 372, 1970. doi: 10.1 1091/T9/TTT.T... 197111970..00 1054466.
[42] M. Huai, C. Miao, Y. Li, Q. Suo, L. Su, and A. Zhang Metric learning from probabilistic labels. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1541-1550, 2018
12

---

[43] G. Huang, Z. Liu. L. D. Maaten, and K. Q. Weinberger. Densely connected convolutional networks
In 2017 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 2261-2269, Alamitos, CA, USA. jul 2017. IEEE Computer Society. doi: 00.109//VPR..221.244. URL https://doi www..eeeeeooopteercceeee.e. www.:eiiittttttooooooo 111110...111PP.... 2017 243
[44] P.J. Huber. Robust estimation of location parameter. The Annals of Mathematical Statisticc,, 35(1):73 101, 1964. doi: 10. /a.121//amm/1177700003
org/ 10. 2214///mm/1177////0/
[45] P. J. Huber. Robust statisties. In International Encyclopedia of Statistical Science, pages 1248-1251. Springer, 2011.
[46] Ishida, I. Yamane, N. Charoenphakdee, G. Niu, and Sugiyama. Is performance of my deep network too good to he true? direct approach to estimating the Bayes error in binary classification. In The Eleventh International Conference on Learning Representations, 2023. WtRpsttps:///ppee het//oorumiid=F22A0yyyyy
[47] U. Javed, K. Shaukat, A. Hameed, F. Iqbal, T. M. Alam, and S. Luo. A review of content-based and context-basett recommendation systems. International Journal of Emerging Technologies Learning (iJET), 16(3):274-306, 2021.
[48] E. Jeon. ViT-PyTorch, 2020.
[49] T. Kailath. The divergence and Bhattacharyya distance measures in signal selection. IEEE Transactions on Communication Technology, 15(1):52-60, 1967. doi: 10.1 11..///O...99..1100000
[50] S. M. Kay. Fundamentals of Statistical Signal Processing, vol. 2: Detection Theory. Prentice Hall PTR, 1998.
[51] D. Kicla, M. Bartolo, Y. Nie, D. Kaushik, A. Geiger, Wu, B. Vidgen, G. Prasad, A. Singh, P. Ringshia, Ma, Thrush, S. Riedel, Z. Waseem, Stenetorp, R. Jia, M. Bansal, C. Potts, and A. Williams. Dynabench: Rethinking benchmarking in NLP. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pages 4110-4124, Online. June 2021. Association for Computational Linguistics. doi: 10.18653/v/20211
maacl-main.333 URL httpt:t///c/aaattooolltaaoo// wwwphhhooogooooggg/// org/2021 .naacl aaaacl-main..... 324
[52] D. P. Kingma and M. Welling. Auto-encoding variational Bayes, arXiv preprint arXiv:1312.6114, 2013.
[53] A. Krizhevsky, G. Hinton, et al. Learning multiple layers features from tiny images. 2009.
[54] P. Kumar. Moments incqualitics of a random variable defined over finite interval. J. Inequal. Pure Appl. Math, 3(3):1-24, 2002.
[55] J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory. 37(1):145-151 151, 1991. doi: 10.1 1551
[56] T. Lissack and K.-S. Fu. Error estimation in pattern recognition via L" -distanneee between posterior density functions. IEEE Transactions on Information Theory, 22(1):34 1976. doi: 10.1109/TIT.197 1055512.
[57] S. Liu, J. Niles-Weed, N. Razavian, and C. Fernandez-Granda. Early-learning regularization prevents memorization of noisy labels. Advances in Neural Information Processing Systems, 33:20331-20342. 2020.
[58] G. Loizou and S. J. Maybank. The nearest neighbor and the Bayes error rates. JEEE Transactions on Puttern Analysis and Machine Intelligence, PAMI-90):254-262. 1987. doi: 10.1109/TPAMI 1987. 4767899.
[59] H. Mania, J. Miller, L. Schmidt, M. Hardt, and B. Recht. Model similarity mitigates test set overuse. Advances in Neural Information Processing Systems, 32, 2019.
[60] R. A. Maronna, R. D. Martin, J. Yohai, and M. Bariiiaa-Barrra.... Robust Statistics: Theory and Methods (with R). John Wiley & Sons, 2019.
[61] A. Menon, S. Rawat, S. Reddi, S. Kim, and S. Kumar. statistical perspective on distillation. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7642, PMLR, 18 24 Jul 2021. URL htthtttss: p/tttpe:///rrooeddings. mlr, www.m.rr..ss... wwtppppeese///eeoo///eeeee html
13

---

[62] Minsker. Distributed statistical estimation and rates of convergence in normal approximation. Electronic Journal of Statisticx. 13(2):5213- 5252, 2019. doi: 10.1214/19-E1S1644. URL https:/:://d
2214/19-EJS1641
[63] E. A. Nadaraya. On estimating regression. Theory of Prohability & Its Applications, (1):1111-44, 1964.
[64] N. Natarajan, I. Dhillon, P. K. Ravikumar, and A. Tewari, Learning with noisy labels. Advances in Neural Information Processing Systems, 26, 2013.
[65] A. S. Nemirovskij and D. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley- Interscience, 1983.
[66] J. Neyman and Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Pupers of a Mathematical or Physical Character, 231 (61(6-7776) -377 1933.
[67] M. Noshad, I.. Xu, and A. Hero. Learning to benchmark: Determining best achievable misclassification error from training data. arXiv preprint arXiv:1909.07192, 2019.
[68] G. Patrini, A. Rozza, A. Krishna Menon, Nock, and L. Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1944-1952, 2017.
[69] J. C. Peterson, R. M. Battleday, T. L.. Griffiths, and O. Russakovsky. Human uncertainty makes classifica- tion more robust. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9617-9626, 2019.
[70] H. Phan. PyTorch_ CIFAR,,, 2021.
[71] Z. Ren, R. Yeh, and A. Schwing. Not all unlabeled data equal: Learning weight data in semi- supervised learning. Advances in Neural Information Processing Systems, 33:21786 21797, 2020.
[72] C. Renggli, L. Rimanic, N. Hollenstein, and C. Zhang. Evaluating Bayes enror estimators on real-worke datasets with FeeBee. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL https//ts:/// //pprree//eeereiieee
[73] T. Sakai, M. C. Plessis, G. Niu, and M. Sugiyama. Semi-supervised classification based classification from positive and unlabeled data. In International Conference on Mmachine Learning, pages 2998-3006. PMLR, 2017.
[74] B. Sarwar, G. Karypis. J. Konstan, and J. Riedl. Item-based collaborative filtering recommendation algorithms, In Proceedings of the 10th International Conference on World Wide Web. WWW '01, page 285-295, New York, NY, USA, 2001. Association for Computing Machinery. ISBN 1581133488 doi: 10.1 1115//71920.320777 URL WtRp.bttps://aa.
org/ 10. 1145/37 1445/371920. 372071
[75] Sekeh, B. Oselio, and A. O. Hero. Learning to bound the multi-class Bayes error. IEEE Transactions on Signal Processing, 68:3793-3800 3807, 2020. doi: 10. 111111PP.020.2220
[76] Shalev-Shwartz and S. Ben- David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
[77] Shlens. tutorial on principal component analysis. arXiv preprint arXiv:1404.1100, 2014.
[78] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. pages 1-14. Computational and Biological Learning Society, 2015.
[79] A. Singh, R. Nowak, and J. Zhu, Unlabeled data: Now it helps, now doesn't. Advances in Neural Information Processing Systems, 21, 2008
[80] H. Song, M. Kim, D. Park, Y. Shin, and J.-G. Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, pages 1-19, 2022. doi:
[81] C. Szegedy, V. Vanhoucke, S. Toffe, J. Shlens, and Z. Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pages 2818-2826, 2016.
[82] M. S. Tanveer. M. U. Karim Khan, and C.-M. Kyung. Fine-tuning darts for image classification. In 2020 25th International Conference on Pattern Recognition, pages 4799, 2021. doi: 10. 10.1109//CPR48806 3021.941222
14

---

[83] R. Theisen, H. Wang. L. R. Varshney, C. Xiong, and R. Socher. Evaluating state-of-the-art classification models against Bayes optimality. Advances in Neural Information Processing Systems, 34:9667-9377. 2021.
[84] R. L. Thorndike. Who belongs in the family? Psychometrika. 18(4))267-276 1953. doi: 10.1007/ BF02289263. / 100700..1.011001 BO07/BB02229263
[85] G. T. P. Toussaint. Feature Evaluation Criteria and Contextual Decoding Algorithmss in Statistical Puttern Recognition, PhD thesis, University of British Columbia, 1972.
[86] K. Tumer and J. Ghosh. Bayes rate estimation using classifier ensembles. International Journal of Smart Engineering System Design, 5(2):95-109, 2003, doi: 10. 10.10800102558113000002 URL httpts //doi. org/ 10. 1000/1025581005500000
[87] J. Unnikrishnan, Haghighatshoar, and M. Vetterli. Unlabeled sensing with random linear measurements. IEEE Transactions on Information Theory, 64(5):3237-322 2018.
[88] X. Wang, Hua, E. Kodirov, D. A. Clifton, and N. M. Robertson. ProSelfLC: Progressive self label correction for training robust deep neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 752 752,761, 2021.
[89] G. S. Watson. Smooth regression analysis. Sankhyā: The Indian Journal Statisticss Series A, pages 359-372 1964.
[90] Q. Wei, L. Feng, H. Sun, R. Wang, C. Guo, and Y. Yin. Fine-grained classification with noisy labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11651- -
1 11660, June 2023.
[91] R. Werpachowski, A. György, and C. Szepesvári. Detecting overfitting via adversarial examples. Advances in Neural Information Processing Systems, 32, 2019.
[92] X. Xia, T. Liu, B. Han, C. Gong, N. Wang, Z. Ge. and Y. Chang. Robust early-leaming Hindering the memorization of noisy labels. In International Conference on Learning Reprexentations, 2021.
[93] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms. arXiv preprint 17x.iv:100..77210 2017.
[94] Y. Yao, T. Liu, M. Gong, B. Han, G. Niu, and K. Zhang. Instance-dependent label-noise learning under a structural causal model. Advances in Neural Information Processing Systems, 34:4409-4420, 2021.
[95] Y. Yao, I. Peng, and M. Tsakiris. Unlabeled principal component analysis. Advances in Neural Information Processing Systems, 34:30452-3044 2021.
[96] K. Yi and J. Wu. Probabilistic end-to-end noise correction for learning with noisy labels. In Proceedings the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pages 7017-7025, 2019.
[97] H. Yuan, N. Xu, Y. Shi, X. Geng, and Y. Rui. Learning from biased soft labels. arXiv preprint Stl::2302.081555 2023.
[98] C.-B. Zhang, P.-T. Jiang, Q. Hou, Y. Wei, Q. Han, Z. Li, and M.-M. Cheng. Delving deep into label smoothing. IEEE Transactions on Image Processing, 30:5984-5996, 2021.
[99] H. Zhang, P. Koniusz, S. Jian, H. Li, and P. H. Tomr. Rethinking class relations: Absolute-rclative supervised and unsupervised few-shot learning In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9432-9441, 2021.
[100] I. Zhang, J. Song, A. Gao, J. Chen, C. Bao, and K. Ma. Be your own teacher: Improve the performance convolutional neural networks via self distillation. In Proceedings of the IEFF//VE International Conference on Computer Vision, pages 3713-3722, 2019.
[101] H. Zhou, Song, J. Chen, Y. Zhou, G. Wang. J. Yuan, and Q. Zhang. Rethinking soft labels for knowledge distillation: A bias-variance tradeoff perspective. In International Conference on Learning Representations, 2021. URL httpht URthttps: httpps://openreviee. net/forumm ? idd widddddgllii gIdd- 5X324
15

---

Appendices
A Related work
well known that the BER of binary classification problem can be achieved by likelihood ratio test [66] and the BER of multiclass classification problem be attained by Maximum a Posteriori (MAP) classifier [50]. The problem of estimating the BER using a dataset has been extensively investigated from the middle of the 20th century [16] the present [13], leveraging different approaches, such as the k-nearest neighbors (NN) method, probabilistic divergence, and bounds the BER. In the early stage, the main approach was derive upper and lower bounds on the BER, while recent work mainly focuses on directly estimating the BER rather than deriving bounds on it.
BER bounds. Several bounds on the BER in binary classification tasks have been proposed using probability divergence and distance metrics. Notable approaches use the Mahalanobis dis- tance 20 [86). the Bhattacharyya distance between two class conditional distributions (20 49 86 the
Chernoff coefficient (a generalization of the Bhattacharyya distance) [4 25 (29], the Henze- Penrose
divergence [6], the Jensen- -aasnnnnh divergence [55], bounds for the min a, b) function 2 39 gen-
cralization of the equivocation bound [1] and of the Bayesian bound [2]. the Mo-distance 85 the
Fano's 's inequality (I5), and the La norm of posterior probabilities [9] Some of these bounds are tight, but they still require estimating the data distribution (e.g., class conditional distributions or posterior probabilities), which may not be practical, particularly for modern data (e.g., images and videos) TO Bounds on the BER were also derived using non non-parametric approaches [16] [1 30 [3], such as the k--N classifier. A remarkable advantage of k-NN classifier for this problem is its distribution- free property to bound the BER (i.e., it works under no assumption on the data distribution). A convergence rate analysis for universal BER estimators was developed in 1 22
Direct estimation of the BER. As an alternative approach to using bounds on the BER, some recent research directly estimates the BER [13 46 67 83]. In particular, the authors in 67 expressed the BER as function of the f-divergence and proposed density ratio estimator to evaluate such an f-divergence that yields the BER. Under various label assumptions, a direct BER estimator was proposed in [46]; this estimator is unbiased and consistent for soft labels, and it has desirable properties. Another direct estimator for the BER was proposed in [[3]. In particular, this estimator uses the relationship between the BER and the miss-classified samples.
Extension to multi-class classification. The extension of the BER in binary classification to multi-class classification has been extensively investigated both in terms of generalizing existing bounds and deriving new approaches. For example, the Chernoff bound [34] the Jensen-Shannol divergence (55), the Fano's inequality (15), the general mean distance (8) the La norm of posterior
probabilities [19], and the generalized Henze-Penrose divergence (75 can be used to derive bounds
on the BER in multi-clas classification problems. Non-parametrie methods [3] 58). such as the
k-NN classifier, can also bound the BER in multi-class classification settings. Bounds based on the
error probability a k-NN classifier in the asymptotic regime were studied [16), and some bounds in the non-asymptotic regime can be found in [10 32
In particular, comparisons of a variety of upper bounds on the BER were studied in [56] 72). and arbitrary tight upper bound was proposed in [2].
Interested readers are referred to 2 [
56 72
16

---

B Proofs and auxiliary results
B.1 Proof of Theorem
1
Proof. By taking the expectation of sooft in
with respect to Px,Y, we obtain
E| Soott (D))
E
max V5 JE[M]]
n
(æ-N)ED
1
max Pr(C j|X) JE[M
n
(x.
E
max [EEM
Pr(C = j(x)
Pe.
(16)
where the second equality follows from (3) and the last equality is due to (2) This shows that shoftt (4) is an unbiased estimator of Pe.
Next, let Us i.s.d. ~ YM:M for all k E [n], and note that Us E [ 1] = u. Define function
f Fu + |0, 10 M as f(U Un) == Ek=1 (1- Uk), which is equivalent to thoot in (4)
Then, for any un E l and for all k E [n]. we have that
sup [f U;-1, the Us+1. un) f(u1,.., u4-1, d441,-.. un) vEll
((1 u:) (1 v))
sup well
(17)
M
By using McDiarmid's 's inequality
23 together with (16) and 17
we arrive at
Pr (Iyssn- Pel 2 = Pr Prf(UU), Un)
(U Un)ll 2)
2nE²
< 2xxp
(18)
(1
1 2
M
By taking n + oo, we obtain
2ne
lim Pr (/vioott Pal 2 < lim 2 exp
= 0,
(19)
(
111 )
which shows that theof: in (4) is consistent estimator of P..
V
By setting E
In in 18 where ò (0, 1), we obtain
2n
11
1
2
Pr
Wsont Pel V
M
In
>
1
8.
(20)
2n
This shows the convergence rate.
The estimator whott in (4) can be viewed as the sample mean of max Dj in D. Since max My ~ Y YM.M from the central limit theorem, as n co, we obtain that
Vn (D'sott
Pe) + (O, Var(1 YM.M))
(0, Var(YN.M)).
(21)
This concludes the proof of Theorem I
17

---

B.2 Proof of Proposition !
We have that Y.M maxje[M] Ky Then, by letting Un i.d. YMM for all E [n], we
Proof.
obtain
Var(wbont)) = Var (1 E( (1
UAA)
k=1
Var (1 Uk)
71
Var(Uk)
n
Var(Yar:rr.
(22)
Moreover, by using the Bhatia-Davis inequality 77. we obtain Var (Yu:м)) = Var (1 YAS:M) ) S
(1 M - P.) Pe since E[pson] Pe. which gives
Var(thsont S (1 M Pe p2
(23)
Finally, maximize the term (1 Po) Pe over 0 S P.
11-
1 M
The maximum is
indeed (1- ) attained by P. (1 ) Hence,
(1
Pe
P2
Var(V)sftt) I
37
72
(1 M
(24)
4n
which concludes the proof of Proposition
B.3
Proof of Theorem 2
Proof.
We start by noting that, by viewing e'sott in (4) as a sample mean of (1-111xm) (1-YMMM).. the estimator
MoBx (Noott D) is median-of-means estimator. It has been shown in 62 that, provided that
E||1 YM:: - 1 < oc, condian-of-meann estimator satisfies
|MoBx (3/s D) Pe S 3 ((Var((MM:a)) [B[]1 YM:M Pa
K
(25)
Var(YM::)
n
K
V n n-K K
with probability at least 1 4e 4c-2 2s for all S K. From 54 eq. (3.8)), since (1 YM:M) e
10, M
1 we have that
1
E|1 YMM Pel P
Po
2P.
M
M
(1
M
(26)
6/3
where the last inequality follows by maximizing Pe (1
Po) (1
M - 2P)) with respect to
18
P. <1 - 37 Substituting (26) into 25
leads to
(1
MMB (WVoiit D) Pal < 3 (Y
s
6v3((VrrYYM..)) )) K
K
(1
K
2 1..3aarYMMM..... Vn K
+ 3/ -Va((YM.M))
V
Vn-K
K
(27)
Under an appropriate choice of n and K (e.g., s. K o(n)), the upper bound in which proves the consistency of MoB (Woott, D).
27
converges to
18

---

For the breakdown point of MoB (t'son, D), we start by observing that, if we have then at most K+1 base estimators ( (Dx))'s in (6) can be affected by these outliers, i.e., they can be bad. In this case, MoBx (V'ottt D) gives a bad estimate since more than half of the base estimators
K+1 2
outliers,
Wsott (Dx) are bad. However, if the number of outliers is smaller than K+1 e.g., | 1,
then the median of disott (Px), & E [K] is not bad estimate since the number of outliers is smaller
than half of the base estimators. Thus, from Definition 3 with K+1 and + T n, we obtain B (MoBx, x (Meot D))
K+1 +.
The proof of the asymptotic normality of MoB (Psoft D) follows directly from 62 Theorem 4]. In particular, if K oo and K n( + oo, it holds that
Vn (MoB (Wsoft, D) P.) S W (0, T Var( Var(YMM.s))
(28)
This concludes the proof of Theorem
B.4 Random permutation noise
One of the most common type of label noises is noise that randomly permutes/shuffles the data labels (27], i.e., we have (z, 7 Dp where Dp denotes the dataset with randomly permuted labels. This noise model can be categorized into two types [27], namely instance pentance-independerr and instance- dependent. The former perturbs the label y with random permutation according to some probability distribution (the extreme noise case, namely unlabeled data or data without correspondence, where the label is permuted with probability
using random permutation matrix, has also been studied extensively (36] 71 73 77 87 951), which is independent of the input features. For example, a comuptiio by instance inn.eneddeddeeeennttt noise to y [0.1, 0.7, 0.2] may result in ý [0.1, 0.2, 0.7] T. The other type of noise, the instance-dependent noise, flips/permutes the labels depending on the instance. For example, the label "car" is more likely be flipped "truck" rather than "cat".
We note that ets in (4) only depends on the maximum value of y, which does not change after that random permutation applied y. This property ensures that seoft is still effective estimator of Pe even when the labels are randomly permuted, as stated in the next theorem.
Theorem Let Dp (a; V= be a dataset that consists of noisy soft labels ú. P.y. where i,úE E [M] is any random permutation matrix of size M x M. Then, weott (Dp) satisfies all of the properties in Theorem and Proposition]
Proof. Since m Yj is permutation-invaaiian with respect to y, it follows that
soo (f(x,, ;.))==) ssaft (f(2;; P.y))=)
siaot (1( 8, ())
(29)
where the first equality follows since D. p.y., and the second equality is due to the permutation- invariance property of the max function. The results Theorem and Proposition then prove Theorem 4
B.5 Proof of Theorem 3
= | X, and ug the unique feature vector (or tensor). We denote by 0 E y the soft label corresponding to ug. i.c., Uy Pr(C 1|X us)...., Pr(C = M uz)] With these definitions, observe that due to the law of large numbers, we have
Proof. Without loss of generality, we let X' = {u,, U2, ........ ug}. where K=
is the cardinality of
lim s(uR) n 200
X uR]
YEY. = ux)
Y =uu]
Ukk
(30)
19

---

where (a) follows from the law of total expectation and (b) is due to the fact that E|Y Y = Y since the noise is zero mean. Now, since for any E [n] there exists & [K] such that æ; Ug. we can write that
lim idx(x;;= = lim idx(uss) 2-000
n-00
arg max [vx)
je[M]]
arg max (Pr(C' j| =u)}
JE[M]
idx (xx):
(31)
where the equality in (a) follows from
30 Then, we can write &DN (Dx) in 12 as
DN (Da)=
Max =x (ύ,, )idx(())))
(32)
When -> co, it follows that
lim VDN (DA)
E 1[x ux (1-Y i (oss))))
E
1 1(x me (1-Te(y) (
E
1(X xxx=
11-Yioi (1-Y (idrwae)
1m1
1(X un) (1-
(1-
Pr(C = -|X -u.))
E
max jE(M]
K
max Pr(C = j|X = us) JE(M]
x= us
Pr(X = uk)
E
max Pr(C== = j|X) JE[M]
Pe.
(33)
where the labeled equalities follow from: (a) the law of large numbers, the assumption that (æ,, 9.) Px "x Y. and using (31): (b) using the law of total expectation; and (c) the fact that E Y = Y since the noise is zero mean. This proves the consistency of v'DN.
The asymptotic unbiasedness directly follows from the consistency together with the assumption of bounded support for the noise. Specifically, since Z, E [a, b) for all ý E [M], we have that
lim E [DDN 220
= E
lim VDN (Da) Ln
P..
(34)
where the first equality follows by the dominated convergence theorem that be applied since | (Px)l (PD)( max{[a),|11 1 + bbb, where and b are the minimum and the maximum value the support of the noise, respectively, and they are both finite. This shows the asymptotic unbiasedness of LDDx((DA)
20

---

We are left to prove the denoising consistency. The denoised label s s(z;) in estimator of y, since
is an unbiased
=x,,,,,,, j=1 1[x,= -Xx=x,)
E
E
1(x; X,
(b)
N,
j= 1(x; = =
(c)
N, N.X.] E
N
(d) E
1
E
X.
N
XX,]
(35)
where the labeled equalities follow from: (a) letting Xj. Y, and Y, for all j E [rx] be independent copies of X, Y, and Y, respectively; (b) introducing a random variable N E [r] that counts the number of X, such that Xj- X, and using the law of total expectation; (c) re-indexing Yk, k E [N] for the N pairs (X,, Yx) such that X; = X;; and (d) the fact that the noise is zero mean.
Note that s (x;) is the average of nwm, noisy labels j''s corresponding to By Hoeffding's 's inequality, we then obtain
21a g2
Pr (1s(2))) ys 22) S 2exp
(36)
(1 17 a b)
(1 a+b)²
Setting E
leads to
2nm;
(1 M a + b)
2
Pr
(s(2;) - U.l
In 8
1
(37)
27
This concludes the proof of Theorem
B.6 Properties of Vggmmi (DDx)
The following proposition defines Vigenic and provides some properties it.
Proposition 2. Let DA = {(,;, D. be a dataset that consists of noisy soft labels ú, -y, + z; with z; f.d.d Pz, such that E = 0. Let c; = arg maggaa[e[[]]] (B)))) Then, the following estimator
Vgenie (DA) = 7 1=1
Σ (1 (7.c.)
(38)
satisfies the following properties:
1. (Unbiasedness): It is an unbiased estimator of the BER;
2. (Consistency): It is a consistent estimator of the BER;
3. (Variance): Var (ggemie (Uge)ie((x)) VariY )+ Variz)
4. (Asymptotic Normality): VnilUgenie (Da) (Da)-Pa) PP) 4 NO Var(YMaas)+
21

---

Proof.
Define the random variable C arg e Y that indicates the index of Y having the largest value, i.e. Cc [aMr y, We have that
n
1 Veenie (D^)]
E
Ycl
71
(a)
E Y
Y
Ycl
max
Y
JEIM
Pas
(39)
where the labeled equalities follow from: (a) the law of total expectation; and (b) the fact that
Y| Y since E|Z] O. This shows the unbiasedness of ('genic
Now, we show the consistency of geenie (Da) Due to the law of large numbers, n - oc, we obtain that
lim genn (DA)= = lim Σ (1
(8,),,)
10000
1=1
E[1 Ycl
E[E[1 Yc|Y]]
E[1 Ycl
Pe.
(40)
which demonstrates the consistency of Vrenie (DA).
We now compute the variance of Ugennic DD)) We have that
genie (Da)
(1 (8)))
n
(1 (y:)ar - (zz))a)
11
Manit (D)
Σ (zi)es.
(41)
1=1
This yields
Var (D))ni((x))) = Var
wson (D)
Σ Ze
i=1
1
Var (Neon (D)) + Var (7)
n
Var(YM:M))
+
Var (Z)
(42)
n
n
where (a) follows from the independence between Y and Z, and the fact that Zj 's (with E (M)
are i..dd; and (b) follows by Proposition [
22

---

Finally, to show the asymptotic normality, we observe that from
41 we have that
n (1 (yi)e - -(z))a))
4 genie (DA)
71
max (yi)} (zi)es je(ad]
max (Ui), - (zi)1 JE[M]
(43)
where the last equality follows since (z+) A (zg)e for all (k, E) [M]2 Since 43 is the sample
mean of n realizations from 1 YM.MM Z, the central limit theorem leads to
(n(ggeeie (Dx) Pe) 4 NO0, Var(1 YMs:M - 2))
No Var(Yar: + Var(2 Z)),
(44)
where the last equality due to the independence between YMαM and Z. This concludes the proof of Proposition 2
C Details on existing BER estimators Additional experiments
C.1 Details on existing BER estimators
C.1.1 k-NN BER bounds [16
Let PNN be the error rate of the 1-nearest neighbor (NN) classifier with samples. Then, for binary classification, follows that for n > 00 [16].
1 ( 1 1 2P
S P. < PNN
(45)
2
The above bounds proved by showing the convergence of the conditional posterior probability of the nearest neighbor to the true conditional posterior probability, For details, we refer an interested reader to [16].
To generalize
to M Mcllassification problems, was shown that for + 0o 16
M 1 M
M
PNN
S S.P.P
(46)
M
In our experiments, chose l as this value provides the tightest bounds among larger values of & [16] 72), and we plotted the upper and lower bounds defined in (46). In particular, in order to evaluate PNN given data samples, we generated true one-hot labels for all data samples from their soft labels by taking the index having the maximum value in the soft labels.
C.1.2 Generalized Henze-Penrose (GHP) divergence BER bounds 75
Consider a parameter p (0. and two distributions fo and f1. Then, the Henze-Penrose (HP) divergence between fo and fi is defined as,
- - (1- dx (2p-111))
( pfo(z)+ (11 -
Dp f1) 4p(1 -pp p)
(47)
appealing feature of Dp is that it can estimated directly from the data using the generalized Frredman-Rafske (FR) statistic [28.75) 775), which uses the Euclidean minimal spanning tree.
Then, for fo and fi with prior probabilities p and
p. the BER is bounded 66]
1
1
2 up f1) < P. < 2 2 "p f1),
(48)
23

---

where
up(fo. = 4p(1 - pfo fi) + (2p 1)²,
(49)
and (p(fo. can estimated based on the minimal spanning tree [6].
To generalize the HP bounds in (48), consider an M-class classification problem with ........ PM as class prior probabilities and class conditional probability densities given by fx(2) f( k), = 1,.... M. Let ((M)(x) = -E Pt.f Then, the generalized Mieze--Penross (GHP)- integral is defined as,
GHP (M) (fr /
fi(x))55()) dx, (())
(50)
where S is the support of J (x)) Let 0, the BER upper bound
J
( da: Then, it was shown in 75 that ((0)(()
M M-1 M
P. 2 2
Σ
Σ
(51)
1=1 1=#+1
and the BER lower bound is
M-1
M M
2M
(M)
Pe
(52)
M
In experiments, plotted the GHP BER upper and lower bounds defined in (51) and 52 Similar to the k-NN BER bounds, we generated true one-hot labels for all data samples before evaluating the GHP divergence Dy. Computing the above bounds requires to evaluate 5/.5) and this can be done by using the generalized FR statistics (for more details, see 75 Section IV.]).
C.2 Additional experiments
10
CIFAR-10
CIFAR-10H
Misclassification rate (%)
8
6
2
ResNet19
ResNet50
VGG19
DenseNet169
VIT-16B
Estimated BER
Models
Figure 5: Misclassification error rates of several classifiers on CIFAR-10 10 and CIFAR- 10H datasets.
In Figure 5 we compare the estimated BER with the misclassification error rate of a few popular neural network models the CIFAR-10 and CIFAR-10H datascts. We chose ResNet [40), VGG 78

---

BER
upper bound
GHP upper bound
McB
GHP Tower bound
NNN kower bound
11.4
014
0.2
0.0
0.3
0.50
0.75
1.00
1.25
1.50
1.75
2,00
0.25
0.50
0.75
1.00
1.50
2,00
0.10
BBRR
0.05
0.225
0.70
11.75
1.00
1.25
1.50
1.77
2,00
01.25
11.00
11.75
1.00
1.25
1.500
1.75
2,00
(a) Soft labels.
(b) Noisy soft labels.
Figure 6: Comparison of MMBx(1'c with the GHP bounds and the k-NN bounds with
k 1. The Gaussian samples are generated according to ((c,o²I)) I2),, where E {1)} is equally likely. We consider Z ~ N 14). (v
{(1, (-1, (-1, uses K = Ivnj, the Euclidean distance for d, and r = 1/5. We iterate the experiments 10 times and plot the average of them.
DenseNet 43 and Vision Transformer (ViT) [24] as classifiers compare with and trained these models on the CIFAR- dataset 11 For the error rate evaluated on the CIFAR-IOF dataset, we followed the same experiment setup for testset images from the soft labels (i.e., the probabilities for each class being associated with the
[46]. under which generated the ground-trutt -trtt labels input image) and evaluated the testset the average of the error rates. Figure [ shows that the error rates on CIFAR 10 from the models are worse than the estimated BER, with the exception of VIT. As noted in (46., the reasons for having a lower error rate for VIT than the estimated BER are mainly due to 1) testset over-fitting and 2) various labeling difficulties the dataset CIFAR-10H that is used for estimating the BER. After compensating for such difficulties on CIFAR-1OH, all models' error rates (evaluated on CIFAR-1OH) worse than the estimated BER; this suggests that the estimated BER may be good estimation since the error rate of any classifier larger than the BER.
rate. We iterated this procedure 20 times and plotted
Figure 6 shows the comparison of MoBx (te) with the GHP and K-NN bounds the BER. For each class c {(1, 1). (-1, (-1,-1) -1),
-1]}, we generated 500 Gaussian samples (Cc, o² to have total of 2, 000 samples. The label noise generated according to Z ~ N (44.). The case of no outliers considered this experiment. We observe that our BER estimator outperforms the other estimators over の² [0.1.2] in both cases of noiseless soft labels and noisy soft labels.
also made performance comparisons varying different parameters (i.e., μ, a² ,2,77 r) in Figures] 7 and 10 Similar to the experiment setting for Figure 6 we generated a total of 2, 000 Gaussian samples with different parameters that are specified the caption of each figure. The effect of ja and x² on the BER estimation is shown in Figures and under different choices of the radius We also provide performance comparisons of our estimator with the other estimators for different values of the noise power of in Figures 9 and 10 Choosing appropriate value for is critical in the estimation the BER as shown in Figure I0 An appropriate value for r can be empirically determined by using the elbow method (84), which is commonly used for choosing the number of clusters in k-meaas clustering algorithms. Using Figure we selected r = 0.2 (elbow point) for the main experiment in Figure 2 Overall, from these figures, observe that our estimator outperforms the GHP and the 1-NN classifier BER bounds in various settings.
g 9
We fine-tuned the official VIT-16B model (pre-trained on imagenet21k) on CIFAR- dataset; for this we used the implementation in (8). Moreover, trained the other models using the implementation in (70]
25

---

BER
NN uppar bound
GHP upper bound
(o
GHP lower bound
L-N lower bound
0.6
0.5
22
11.4
0.2
0.2
0.0
0.25
0.50
1.00
1.25
1.73
2,00
0.25
0.75
1.25
1.50
1.75
2.00
0.10
[NER
0.20
0.30
0.75
1.00
1.25
1.30
1.7
2.00
0.25
0.30
0.75
1.00
1.25
1.50
1.75
2.00
(a) r 0.3.
(b) 0.4.
Figure 7: Comparison of (1 with the GHP bounds and the k-NN bounds with
A = 1. The Gaussian samples are generated according to A(c, 12), where c E ((,, 1)) (-), (-14, -u), (1,-H)) -4} with equal probability. We consider Z (4, MоBx (V/c) uses K = vnl. the Euclidean distance for d, and r E {0.3, 0.4). We iterate the experiments 10 times and plot the average of them.
N-N bound
GHP upper
McBa/ec)
GHP
0.5
0.1
3.0
0.5
1.0
1.5
2.0
2.5
3.0
0.11
0.5
1.0
1.5
2.0
3.0
0.10
IBER
INRR
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
1.5
2.0
3.0
(a) r 0.3.
(b) = 0.4.
Figure 8: Comparison of MoBx with the GHP bounds and the k-NN bounds with A = 1. The Gaussian samples are generated according to o2c, where E with equal probability. We consider Z N (0, la). Mo uses K /nl, the Euclidean distance for d, and r {0.3, 0.4). We iterate the experiments 10 times and plot the average them. As expected, a larger value of Figure 8b yields better performance than smaller value of in Figure Sa
26

---

BER
bound
GHP bound
MoBx((kc
GHP bound
bound
0..6
0.5
0.4
0.1
0.2
11.00
0.0
01.20
0.30
0.775
1.00
1.25
1.50
1.70
2,00
0.25
0.50
0.75
1,00
1.25
1.50
1.75
2,00
[BER
INER
0.05
0.25
0.50
0.75
1.00
1.25
1.0
1.75
2,00
0.25
0.30
0.75
1.00
1.25
1.50
1.75
2.00
(a) 02 0.3.
(b) 02 0.4.
Figure 9: Comparison of MoBx with the GHP bounds and the k-NN bounds with
k 1. The Gaussian samples generated according N(ce, I2), where
{H, n1) (-H, (-H, -M), (p, with equal probability. We consider Z (0,44) MMB)( uses K = Iv the Euclidean distance for d, and 0.2. We iterate the experi- ments 10 times and plot the average of them. In both figures, the performance of our BER estimator at the extreme values of is worse than the performance of the other estimators; this is due to an inappropriate choice of r.
BER
NN bound
GHP bound
(oBa
GHP ooer bound
NN lower bound
0.1
0.4
0.6
0.7
0.50
0.20
DER
0.02
0.00
0.00
0.
0.7
(a) 02 0.3.
(b) 02 0.4.
Figure 10: Comparison of MoB ( with the GHP bounds and the k-NN bounds with k with respect to the cluster radius r. The Gaussian samples are generated according to (ec, Iz). where e E {(1, 1-1, (1).. We consider Z N (0, 1z.4). M uses K Lvn and the Euclidean distance for d. We iterate the experiments 10 times and plot the average of them.
27


Reviews:
[{"review_id": "JEdbs3Ubsu", "reviewer": "Reviewer_7qAC", "summary": "This paper aims to design a tighter estimate for the Multi-class classification error. The paper analyzes several theoretical aspects of the suggested Bias Error rate  estimator, including its consistency, unbiasedness, convergence rate, variance, and robustness. Moreover the authors utilize a denoising method to reduce label noise if such is present and improve robustness to the outliers by incorporating the median-of-means estimator. They validate the effectiveness of our theoretical results via experiments both on synthetic data under various noise settings and on real data (CIFAR-10H, Fashion-MNIST-H and MovieLens -- movie recommendation dataset) \n", "questions": "I would love the authors to explain what is the impact of their work and experiment (maybe in Discussion/ Conclusion section that is currently missing).", "limitations": "My main concern is that the paper does not have a real impact on more complex Deep Learning tasks of NLP and Computer Vision.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper raises an important issue of estimating performance limit of the multi-class classifier.  It provides thorough theoretical analysis, backed up by some experimentation.  ", "weaknesses": "I'm struggling to see an impact of this paper. It aims to demistify optimal performance of multi-class classification, but I did not see any illustration of this in the paper. I would expect to see performance of SOTA method on a complex task (e.g., ImageNet) vs. the provided estimator, but the paper uses relatively easy classification tasks for illustration of the bounds. So not clear what is the applicability of this paper for more challenging tasks of Computer Vision and NLP. Also I would expect some theoretical derivation on what is a good feature space for which the suggested denoising holds. Note that the denoising itself is not novel, and seems a bit ad-hoc solution to improve the accuracy of the estimator. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their time and effort put into thoroughly reading and reviewing our manuscript.\n\nRegarding the impact/applicability of our paper. We would like to first note that we did consider a complex classification task for the evaluation of our bounds using the MovieLens dataset. This is indeed a challenging task in computer vision where a multi-modal network model classifies a two-hour movie (input feature) with audio. None of the SOTA Bayes error rate (BER) estimators would be applicable to such a complex task since they either require to find the data distribution/divergence or have a prohibitive complexity. Differently, our estimator simply requires labels and a denoising method. Second, we would like to point out that the reason we evaluated the bounds for some easy classification tasks (e.g., Gaussian noise) was to showcase the effectiveness of them in estimating the BER in scenarios where this is indeed known. In summary, we agree that  including more experiments on complex tasks would strengthen the paper. However, we also feel that this would go beyond the scope of this single paper.\nAs also suggested by another Reviewer, in the revised version of the paper, we will add a Conclusion section with such a discussion.\n\nRegarding the denoising method. The results presented in this paper show that the proposed denoising method is consistent for any (finite) feature space in the asymptotic (see Theorem 3). We agree that finding a good feature space could be the next natural step, and we thank the Reviewer for this comment. In particular, one could analyze the rate of convergence of our BER estimator paired with the denoising method as a function of the characteristics (e.g., cardinality, distribution) of the feature space. We will add this discussion in the Conclusion section in the revised version of the paper. Finally, we would like to note that our denoising technique is theoretically universal (see Theorem~3) and hence, we feel that it is not an ad-hoc solution. Of course, if we have knowledge about the noise distribution in the dataset, then we can improve the accuracy of the estimator, which might be indeed an ad-hoc solution. However,  we here make a very general assumption on the noise distribution (i.e., i.i.d. and zero-mean). In summary, we agree that the denoising technique can be further theoretically analyzed, but we do not feel that this represents a weakness of our work."}, {"review_id": "DKsTUXtXjd", "reviewer": "Reviewer_2nax", "summary": "This paper proposes a few methods for estimating Bayes error rates of multi-class classification in different scenarios. The proposed method generalize the previous soft-label approach for binary classification [Ishida et al., 2023] and also extends it for robustness to label noise and outliers. The first extension uses the median-of-means in place of the ordinary average for better robustness, and the second one uses the feature-wise average assuming the features are discrete. The third one uses a Nadaraya-Watson estimator with the Parzen kernel for incorporating data points near each point. The paper provides theoretical analyses for the estimation errors, convergence rates, and the robustness guarantees. Finally, the paper presents experiments using synthetic data and three benchmark datasets demonstrating the superiority of the proposed methods.", "questions": "### Major comments\n- How does one choose $r$? More importantly, how did the authors choose it in the experiments?\n- The proposed denoising method essentially estimates the class posterior probability using the kernel method. What is the motivation for using this method when there are many other classification methods performing well?\n- The footnote on page 2 says \"We assume that $\\mathcal{X}$ is a finite set, but several of our results easily extend to the case when $\\mathcal{X}$ is an infinite set.\" Having a finite $\\mathcal{X}$ is very restrictive. Why not work on the infinite case in the first place if the extension is easy? What about the continuous case?\n\n### Minor comments\n- Line 137, \"$\\operatorname{rad}(\\theta)$ is the vector consisting of $L$ radiuses along the main axes of the largest $L$-dimensional ellipsoid in replaced by outliers.\": I could not understand this. What are the $L$ radiuses and the vector consisting of them, more precisely?\n- Lines 164-165, \"For example, setting $K = \\ln n$ leads to a higher breakdown point (and hence, is more robust) than setting $K = \\sqrt{n}$.\" Doesn't a larger $K$ have better robustness?\n- Line 178, \"We assume that z has i.i.d. components each with zero mean (without loss of generality).\" I think this does lose the generality.\n- In footnote 3 on page 5, is the definition of sub-Gaussianity correct?\n- I am not very comfortable to call the method in Definition 6 a \"nearest-neighbor\" method because it uses a fixed kernel (with a fixed $r$). I would call it a Nadaraya-Watson estimator with the Parzen window kernel.\n- I suggest using different letters for $P_e$ and $P_e(\\cdot)$.", "limitations": "A limitation is that the paper assumes that the set of features is finite.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written and pleasant to read.\n- The extensions to the noisy cases including the one with hard (one-hot) labels may be practically useful because many datasets do not have soft labels.\n- The use of the median of means to this problem seems interesting. The theoretical results about this part are also insightful.\n- The experiments show the clear superiority of the proposed method over the baseline methods.", "weaknesses": "- The multi-class extension when soft labels are provided seems straightforward.\n- The denoising method in Eq. (11) is a bit disappointing because it heavily relies on the assumption that the features are discrete.\n- The denoising method in Definition 6 could be applied to any $\\mathcal{X}$ with a distance metric, but this essentially estimates the conditional probability $P_{Y|X}$, which contradict the following claim: \"This is an appealing feature of our work, different from taking a plug-in approach that first estimates the istribution from which the data is drawn, and then evaluates the BER. Indeed, our BER estimators, which are proved to be unbiased, consistent and robust to label noise and outliers, do not require the estimation of the data probability density to perform an effective BER estimation.\"\n- Regarding the previous point, if the method in Definition 6 is no better than the SOTA method in the conditional probability estimation, the estimate will be an upper bound of the SOTA score (and the Bayes error). However, it is not convincing to say the proposed method, which looks like a classical method, is better than the SOTA method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their thorough reading of our manuscript, and for the positive assessment of our contribution.\n\nWeakness 1. We agree that the multi-class extension may seem straightforward, but we also feel that this is not a weakness. Indeed, it is just the starting point for further analysis of the Bayes error rate (BER) estimator. Moreover, one needs to formally prove the theoretical properties of this estimator (Theorem 1) before exploring more advanced estimators (e.g., with denoising or robust version).\n\nWeakness 2. The motivation to consider features that are discrete mainly stems from the fact that in practice many classification problems utilize such features (or quantized values from real-valued features). As we pointed out in the footnote on page 2, one can easily extend several of our results on discrete features to real-valued ones (see also our response to Major Comment 3). For example, as the Reviewer commented, the estimator in Definition 6, which extends the one in eq.(11), works well for real-valued (as well as for discrete or mixture valued) features.\n\nWeakness 3. In our problem setting, the soft labels are available and they may be corrupted by some noise. In particular, the soft labels contain the value of $P_{Y|X}$ with noise; our proposed approach reduces the noise effect in the labels, instead of estimating the data distribution. This was the main reason of the sentence. We feel that, although the denoising method in Definition 6 applied to one-hot labels is equivalent to estimating the conditional probability, our approach proposes a novel perspective which could lead to new directions to effectively estimate the BER. Denoising methods have been largely studied and applied to several signal processing problems; this paper shows that they are effective also for BER estimation.\n\nWeakness 4. We believe that the considered SOTA BER bounds, namely the GHP and the $k$-NN error, leverage effective methods for estimating either the conditional probability or the divergence between the class conditional distributions. In this sense, our evaluations show that we outperform SOTA methods. That said, we agree with the Reviewer that a comparison with an additional approach that uses a SOTA technique for estimating the conditional probability, and then uses this to evaluate the BER would validate more our statement. We will add this comparison in the revised version.\n\nMajor Comment 1. The parameter $r$ is a hyperparameter that should depend on the data feature space and on the underlying classification problem. Thus, it is not possible to choose an optimal $r$ before we look at the data and problem, and finding an optimal $r$ is a difficult task in general. In our experiments, we did an empirical search of the value of $r$ in a heuristic way. We chose the value of $r$ at the point where the estimated BER becomes stable (see Figure 9 in the supplementary material). The heuristic method that we used to find $r$ is similar to the elbow method for finding the number of clusters in $k$-means clustering algorithms.\n\nMajor Comment 2. The main motivation for proposing our method lies in exploring new types of labels, i.e., the soft labels, which are starting to be utilized in many applications. By means of Theorem 1, using soft-valued labels with noise, we can estimate the BER by reducing the noise effect instead of estimating the data distribution, which is the approach pointed out by the Reviewer. We believe that for \"many other classification methods performing well\" the Reviewer intends methods based on estimating the class posterior probability. The main reason why we did not focus on such estimators is due to the hardness of estimating the data distribution if the data is complex or has high-dimensionality. Instead, our estimator just uses a cluster-like method that is applicable to most dataset (see also Remark 2). In the revised version, we will add such discussion.\n\nMajor Comment 3. We believe that the assumption of having features that are discrete is somehow without loss of generality in practice. Indeed, several classification problems utilize discrete features, or quantized values from real-valued features. This is the main reason for our assumption. That said, we highlight that Theorem 1 and Theorem 2 also hold for the infinite feature space. Theorem 3 is the only result that we should carefully analyze for the case of infinite feature space. However, we feel that this is doable. In the revised version, we will add this.\n\nMinor Comment 1. Any $L$-dimensional ellipsoid (after rotation) can be defined as $\\frac{x_1^2}{a_1^2} + \\cdots + \\frac{x_L^2}{a_L^2} = 1$. The $L$ radii (and not radiuses) are $\\{a_1, a_2, \\cdots, a_L\\}$. In the $2$-dimensional space, one can imagine that an ellipsoid has $2$ main axes defining it, and the radii are the half length of each main axes in the ellipsoid. \n\nMinor Comment 2. Yes, a larger $K$ gives more robustness; $K=\\ln n$ and $K=\\sqrt{n}$ should be interchanged. We will fix this in the revised version.\n\nMinor Comment 3. We believe that the assumption of zero mean noise is without loss of generality (wlog). If a noise distribution has a non-zero mean, we can subtract the mean of the noise from the noise distribution, which then becomes zero mean. However, the assumption of i.i.d. is not wlog; we feel that this may be the source of confusion for the Reviewer. In the revised version, we will clarify that only the assumption of zero mean is wlog.\n\nMinor Comment 4. We will fix the definition of a $\\gamma^2$-sub-Gaussian random variable, i.e., a random variable $X$ satisfying $\\mathbb{E}[e^{\\lambda (X-\\mathbb{E}[X])}] \\leq e^{\\frac{\\lambda^2 \\gamma^2}{2}},~\\forall \\lambda \\in\\mathbb{R}$.\n\nMinor Comment 5. We will refer to it as Nadaraya-Watson estimator with the Parzen window kernel.\n\nMinor Comment 6. We will replace $P_e(\\cdot)$ with $\\mathcal{E}(\\cdot)$."}, {"review_id": "h0mfxJXWm4", "reviewer": "Reviewer_iHwx", "summary": "This paper studies the estimation of the Bayes error rate (BER) in the multiclass classification problem. BER is the best classification error (in terms of expectation) that can be achieved by the Bayes optimal classifier. First, this paper studies the soft labels case, where the direct extension of the estimator proposed by Ishida et al. [ICLR2023] can be shown to be valid in the multiclass case. Next, this paper studies the case where the soft labels are noisy and proposed the median-of-means estimator to improve the robustness. Furthermore, the denoise estimator cluster-based BER estimators are also proposed. Experiments are also provided to justify the usefulness of the proposed methods.", "questions": "1. Regarding Section 3.1, it is still not clear to me why having a higher value of the breakdown point guarantees more robustness of the estimator (Lines 139-141). What is the meaning of robust here? Does it mean a more accurate estimator under high noise? \n2. I feel Definition 3 is quite difficult to interpret and more discussion could be useful for readers to grasp the importance and how to use Definition 3. I failed to fully appreciate it and would like to ask some questions. \n- 2.1 What is definition of $\\mathcal{D}^{(\\kappa + \\tau)}$?     \n- 2.2 How to interpret the meaning of Eq. (5)? Is there an intuitive explanation of the value of the breakdown points?\n- 2.3 Why $B(\\psi_\\mathrm{soft}) = \\frac{1}{n}$ is not robust? Why we can conclude that this makes the estimator not robust (Line 143)? What number of $B(\\psi)$ is robust?\n3. Questions about Figure 2 experiments:\n- 3.1 I don't see $\\psi_\\mathrm{soft}$ but rather $MoB_K(\\psi_c)$, is this a typo? If so, which methods are compared? I think it is also useful to see the performance of other proposed estimators as well. \n- 3.2  Is it reasonable to use $k=1$ for $k-NN$ bound? I am not familiar with this method but I feel $1$-nearest neighbor may not be robust enough.\n- 3.3 How hyperparameter selection is carried out? I feel the choice of $K=44$ for the proposed estimator is quite unintuitive and was wondering about the sensitivity of this hyperparameter.\n4. Is there a theory to justify the statistical properties of the cluster estimator (15)? If not, is there a way to theoretically validate this estimator?\n5. It is difficult to know the accuracy of BER estimation from Table 1. Is it possible to also put a reference of a model trained for these classification tasks similar to Figure 4 in Ishida et al? \n6. It is discussed that MoB estimator is more robust and therefore gives lower value in Table 1. I was wondering if it is possible to have an outlier that has a low value also? \n\nTypo:\n1.Line 229: nosy -> noisy?\n2. In some places $MoB$ is used instead of $MoB_K$, e.g., legend in Figure 2 and some other places. Maybe we should unify it if this is not intentional.", "limitations": "I have no further things to add here. Please see the weaknesses and questions section for some discussions on limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Writing is easy-to-follow: paper motivation, objectives, and solutions are clear.\n2. Proposed methods are intuitive, easy to implement, and theoretically guaranteed. Many estimators are provided for different use cases.\n3. I found the discussion about the robustness of the estimator $\\psi_{\\mathrm{soft}}$ interesting and the proposed median-of-BERs estimator to mitigate this problem is theoretically guaranteed and practically effective in experiments. In theory, I found the discussion in Lines 158-166 provides interesting comparisons between $\\psi_{\\mathrm{soft}}$ and its MoB estimator.\n4. Experiments are convincing to show that the extension beyond straightforward estimator $\\psi_\\mathrm{soft}$ (MoB, cluster, denoising)can significantly outperform $\\psi_\\mathrm{soft}$.", "weaknesses": "1. Experiments to compare other methods may not be sufficient. In my understanding, only experiments with synthetic datasets with limited hyperparameter choice are conducted to justify the superior of the proposed methods (result in Figure 2). Additional experiments in Appendix C are also only synthetic datasets with the same hyperparameter choice as Figure 2.\n2. Evaluation of the non-synthetic dataset is difficult to know if the Bayes error rate is well estimated, as also suggested in the paper that the labels themselves can be unreliable because of human errors (as discussed in Lines 312-314). But this issue is very problematic by itself and I have no idea how to better deal with this. \n3. Soft labels can be restrictive in many scenarios which may make the proposed method prohibitive. Nevertheless the cluster estimator sounds in (15) reasonable as a good heuristic for BER estimation.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their thorough reading of our manuscript and their effort in carefully reviewing it.\n\nWeakness 1. We agree with the Reviewer that comparisons with SOTA BER bounds are performed only on synthetic datasets. However, this is not due to a limitation of our approach, but rather to the lack of SOTA BER estimators that are applicable to complex classification tasks.  SOTA BER estimators either require to find the data distribution/divergence or have a prohibitive complexity. Instead, we feel that our BER estimation methods are well-suited for such challenging tasks, as we have shown for the MovieLens dataset. That said, as the Reviewer has also suggested, we are training a model using the benchmark and real-world datasets in Table I. Unfortunately, we could not obtain the results by the time this rebuttal was due, but we will incorporate them in the revised version.\n\nWeakness 2. It is true that labels can be unreliable, and this is one of the major challenges in understanding if the BER is well estimated.  This is the main motivation behind our contribution of proposing denoising methods to reduce the noise that can corrupt the data labels.  To the best of our knowledge, this concept of leveraging denoising methods for BER estimation is new. Our results also suggest that this technique is effective and hence, we feel that it could be well-suited to mitigate the unreliability aspect of the data labels.\n\nWeakness 3. It is true that currently soft labels are less used compared to hard labels. However, we feel that the use of soft labels is growing considerably (see first paragraph in Section 3). In Section 4.2, we have also shown that the noisy soft label framework can be used to study the case of one-hot labels. This study leads to the BER estimator in eq.(15), which the Reviewer deems reasonable.\n\nQuestion 1. We consider robustness to outliers, where an outlier is a data sample that is corrupted by high noise. The breakdown point captures how robust a model is with respect to outliers. For example, the sample mean (i.e.,  an estimate of the mean of $X$, which is given by $\\hat{\\mu} = \\frac{1}{n}\\sum_{i=1}^n x_i$ where {$x_i$}$_{i=1}^n$ is a set of realizations of $X$) would fail to estimate the true mean even for the case when there is a single outlier (e.g., $x_i = \\infty$ or an $x_i$ with a value very different from the true mean). Thus, the sample mean has a breakdown point equal to $\\frac{1}{n}$, meaning that one outlier can break the estimate. Differently, the median is more robust since it has a breakdown point of $\\frac{1}{2}$, i.e. half of the samples need to be outliers for breaking the estimate. \n\nQuestion 2.1. Per Definition 3, we have that $\\mathcal{D}^{(\\kappa + \\tau)} =$ {$ D_1,\\ldots,D_{\\kappa+\\tau} $}.\n\nQuestion 2.2. Eq.(5) quantifies the breakdown point for an estimator $\\psi: \\Omega^{\\tau+\\kappa}\\to\\Theta$. An estimator $\\psi$ breaks if $\\psi(\\mathcal{D}^{(\\kappa+\\tau)})$ -- i.e., $\\psi$ evaluated on the clean dataset with $\\kappa + \\tau$ data samples -- changes of at least $||\\mathsf{rad}(\\Theta)||$ when $\\tau$ clean data samples are replaced with $\\tau$ outliers. The breakdown point is defined as the minimum value of $\\frac{\\tau}{\\tau+\\kappa}$,  i.e., the ratio between the number of outliers ($\\tau$)  and the total number of data samples ($\\kappa + \\tau$), such that $\\tau$ outliers are sufficient to break $\\psi$.\n\nQuestion 2.3. Per Definition 3, the breakdown point (see also our response to Question 2.2) is the minimum value of $\\frac{\\tau}{\\tau+\\kappa}$ such that $\\tau$ outliers suffice to break the estimator $\\psi$. In this sense $B(\\psi_{{\\rm{soft}}}) = \\frac{1}{n}$ is not robust. In general, $\\frac{1}{2}$ is the maximum value of a breakdown point.\n\nQuestion 3.1. This is a typo and we will fix it: in the caption, it should be $\\mathsf{MoB}_K (\\psi _{\\mathsf{C}})$. Among the proposed estimators, in Figure 2 we only evaluated $\\mathsf{MoB}_K(\\psi _{\\mathsf{C}})$. This is because we observed that it performs well with respect to SOTA methods and hence, we omitted the other estimators.\n\nQuestion 3.2. The optimal value of $k$ is not known and this might be one of the reasons for which generally, it is set to $1$. Moreover, the value of $k$ should be a small fraction of the total number of samples, and this could be another reason for setting it to $1$. That said, it may happen (and this is the case in the asymptotics) that increasing $k$ leads to a more accurate BER estimation. In the revised version, we will also provide the BER curve relative to the optimal value of $k$ (which we will find numerically).\n\nQuestion 3.2. We chose $K=\\lfloor \\sqrt{n} \\rfloor$ based on Theorem 2, which shows that if $K<o(\\sqrt{n})$ and $n\\to\\infty$, then $\\mathsf{MoB}_{K}$ is asymptotically normal. Thus, we chose $K$ to be large enough (for robustness), yet smaller than $\\sqrt{n}$.\n\nQuestion 4. We did not investigate the statistical properties of the cluster estimator in eq.(15); this is an interesting future direction. As Reviewer 2nax pointed out, this estimator resembles the Nadaraya-Watson estimator with the Parzen window kernel. Thus, we believe that a theoretical validation of the estimator in eq.(15) may be doable.\n\nQuestion 5. This is a great suggestion! We have started working on this, but we could not obtain the results by the time this rebuttal was due. We will incorporate these suggestions in the revised version.\n\nQuestion 6. In general, there might be outliers that lead to lower values of the estimated BER. However, since the labels belong to $[0,1]$ and the estimated BER values in our examples are very small ($0.004\\sim0.04$), we believe that outliers with large values would be more impactful on the final estimate than outliers with small values. For instance, if the true estimate is around $0.05$, outliers with a smaller value than this might not be even considered as outliers. \n\nTypo 1 and Typo 2. We will fix these in the revised version of the paper."}, {"review_id": "JSsjmMmfKP", "reviewer": "Reviewer_HZ6f", "summary": "This paper tackles the important problem of performance estimation in a multi-class setting. The contributions come in the form of several Bayesian Error Rate estimators for different multi-class variants. Several theoretical guarantees are provided throughout the paper, as well as empirical results on synthetic and real dataset.", "questions": "* Can the framework be extended to multi-label classification?", "limitations": "Not applicable.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "# Motivation\nThe problem of estimating and validating the performance of a classifier in a multi-class setting has been a hot topic in Machine Learning. As such, the results provided in this paper are of prime interest for the ML community. Estimating the BER can lead to a better understanding of the multi-class problem and to novel methods for such setting.\n\n# Completness\nThe main strength of this paper resides in providing theoretical results for various settings. The first result is provided for the vanilla case of multi-class learning, where the data is drawn i.i.d. from a hidden distribution. The authors then provide a robust version of the previous result. Finally the paper provides several adaptation of the previous results to the noisy setting, i.e. when noise is added to the labels.\n\n# Experimental results\nThe experimental section provides extensive empirical validation of the theoretical results. Several synthetic and real-world datasets are analyzed and discussed in Section 5 thus shedding light on the benefits of the proposed estimates.", "weaknesses": "# Clarity\nWhile the main motivations are easy to follow, and the paper is overall very-well organized, in several occasions definitions and notations are poorly introduced. In lines 76-78, the definition of Y is misleading since it uses the same notation as in multi-class multi-label learning, particularly since no assumption is made on c and how it is retrieved from y. In line 79, it's not clear what $e$ in $P_e$ stands for and how it is related to the definition that follows.\n\nIn line 86, \"an optimal classifier.\" implies that several classifiers can achieve BER. In other words, looking at the problem from an optimization problem point of view, it means that there are several global minima exist. I'm not quite sure I fully grasp the interest of such an assumption.\n\nIn line 111 the notation $Y_{M:M}$ is used without being properly introduced before or in the remainder of the paper.\n\nIn Definition 4, it's unclear wether an assumption on class distribution exists when defining the K subsets. The absence of such an assumption might explain the trade-off discussed in line 163, in which case it should be clearly noted in the paper.\n\nI'm not quite sure I understand the role of paragraph Notation (lines 65 to 71), when most of the notations are loosely introduced in the remainder of the paper.\n\nEquation (11) is quite puzzling. If I'm reading it right, the denoise estimator is based on samples that have the same exact $\\bf x$, i.e. it implies that there are duplicated data in the learning dataset, which seems odd compared to the i.i.d. assumption of line 76. The denoise estimator of Equation (14) seems like a better and more realistic choice.\n\n# Conclusion\nWhile the experimental section provides several discussions on the proposed estimators, I strongly think that a Conclusion section is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their time and effort put into reading and reviewing our manuscript.\n\nClarity 1. The focus of our paper is on multi-class single-label learning, where each data sample is associated with only one true class. \nOur rationale behind representing $\\mathbf{y}$ as a vector stems from the fact that we consider soft labels and hence,  $\\mathbf{y}$ provides the soft-valued information of each class (see eq.(3)). \nThe Bayes error rate (BER) is denoted with $P_e$ (see Definition 1), where the subscript $e$ stands for error.\n\n\nClarity 2. We define a classifier as optimal if it achieves the BER that is unique (i.e., there is only one global minimum).\nHowever, there may exist several classifiers that achieve the BER. \nFor example, if two different classifiers (with different complexity or algorithm) achieve the BER, both would be considered as optimal. \nThis is the reason for using the wording ``an optimal classifier''.\n\nClarity 3. We defined $Y_{M:M}$ in the Notation (lines 69 and 70).  In particular, $Y_{M:M}$ is the $M$-th order statistic of $\\mathbf{Y}$, that is,  the largest value of $\\mathbf{Y}$.\n\nClarity 4. Definition 4 is just a definition, which holds without any assumption on the class distribution. However, in Section 3, we consider the case of soft labels and hence, Theorem 2 holds under this assumption. In the revised version of the paper, we will add this assumption in the statement of Theorem 2.\n\nClarity 5. We acknowledge that part of the notation introduced in lines 65-71 is repeated in the paper and may be familiar to an audience in the machine learning community. However, we believe that these few lines clearly introduce the reader to some notation that will be extensively used throughout the paper.\n\nClarity 6. We made the assumption that the feature set $\\mathcal{X}$ is finite, which implies the potential existence of duplicated data samples with a non-zero probability. However, this does not create any conflict with the i.i.d. assumption. An illustrative example is the i.i.d. sampling from the uniform distribution supported on {1, 2, 3}; each sample data can have one of these three values with equal probability and two different data samples can have the same value. As another example, in the MovieLens dataset in our experiment, two different users can give a different rating to the same movie.\n\nConclusion. We thank the Reviewer for this suggestion on which we agree. We will make sure to add a Conclusion section in the revised paper.\n\nQuestion. This is a good question. Extending our framework to multi-label classification is a very interesting area for future work. \nTo the best of our knowledge, several metrics (other than the BER) have been adopted for multi-label classification. Examples are the exact match ratio, the F1 score, and the Hamming loss. We believe that extending our framework to estimate the minimum Hamming loss of multi-label classification is not too challenging. \nHowever, extending it to estimate the other metrics may not be straightforward and may require the development of new tools."}]

Author rebuttal:

Meta-review: This seems to be classical "borderline" paper, and all reviewers (more or less) share this opinion. There are several interesting aspects, like the novel robust estimator proposed that comes with some theoretical performance guarantees. On the other hand, there are also several more critical remarks, such as lacking clarity regarding the "true" depth and impact of this work. 
There was quite some discussions among reviewers and authors, and during these discussions several critical points raised by the reviewers could be addressed, at least up to a point where it is likely that an improved final version of this paper could be accepted.
Therefore, I recommend acceptance, but at the same time I would like to encourage the authors to improve several parts in the final version of the paper according to the discussions.
Decision: Accept (poster)