Evaluating State-of-the-Art Classification Models Against Bayes Optimality
Authors: Ryan Theisen
Huan Wang
Lav R. Varshney
Caiming Xiong
richard socher
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayes error
normalizing flows

Abstract: Evaluating the inherent difficulty of a given data-driven classification problem is important for establishing absolute benchmarks and evaluating progress in the field. To this end, a natural quantity to consider is the \emph{Bayes error}, which measures the optimal classification error theoretically achievable for a given data distribution.  While generally an intractable quantity, we show that we can compute the exact Bayes error of generative models learned using normalizing flows. Our technique relies on a fundamental result, which states that the Bayes error is invariant under invertible transformation. Therefore, we can compute the exact Bayes error of the learned flow models by computing it for Gaussian base distributions, which can be done efficiently using Holmes-Diaconis-Ross integration. Moreover, we show that by varying the temperature of the learned flow models, we can generate synthetic datasets that closely resemble standard benchmark datasets, but with almost any desired Bayes error. We use our approach to conduct a thorough investigation of state-of-the-art classification models, and find that in some --- but not all --- cases, these models are capable of obtaining accuracy very near optimal. Finally, we use our method to evaluate the intrinsic "hardness" of standard benchmark datasets.

Evaluating State-of-the-Art Classification Models Against Bayes Optimality
Ryan Theisen*
Huan Wang" Salesforce Research
University of California, Berkeley theisen@berkeley.co
haan, wangesalessorce.........o. com
Lav R. Varshney University of Illinois tibana-Champaic aarshney@illinoke edu
Caiming Xiong
Salesforce Research
cxiong@saleefooceecco com
Richard Socher you.com
rsocherêgma i com
Abstract
Evaluating the inherent difficulty of given data-driven classification problem is important for establishing absolute benchmarks and evaluating progress in the field. To this end, natural quantity consider is the Bayes error, which measures the optimal classification error theoretically achievable for given data distribution. While generally intractable quantity, show that can compute the exact Bayes error of generative models learned using normalizing flows, Our technique relies on fundamental result, which states that the Bayes error invariant under invertible transformation. Therefore, we can compute the exact Bayes error of the learned flow models by computing for Gaussian base distributions, which can be done efficiently using Holmes-Diaconis. Diaconis-Ross integration. Moreover, we show that by varying the temperature of the learned flow models, we can generate synthetic datasets that closely resemble standard benchmark datasets, but with almost any desired Bayes error. We use our approach conduct thorough investigation of state-of-the of-the-art classification models, and find that in some but not all cases, these models are capable of obtaining accuracy very near optimal, Finally, we use our method to evaluate the intrinsic "hardness" of standard benchmark datasets.
Introduction
Benchmark datasets and leaderboards are prevalent in machine learning's s common task framework [8]; however, this approach inherently relies relative measures of improvement. It may there- fore be insightful to able to evaluate state-of of-the-ar art (SOTA) performance against the optimal performance theoretically achievable by any model [34]. For supervised classification tasks, this optimal performance is captured by the Bayes error rate which, were it tractable, would not only give absolute benchmarks, rather than just comparing previous classifiers, but also insights into dataset hardness [14, 38] and which gaps between SOTA and optimal the community may fruitfully try to close.
Suppose we have data generated as (X, Y) p. where E Rd. Y E y = (1...., K) a label and p is a distribution over Idd x y. The Bayes classifier is the rule which assigns label to an
"gqual contribution.
Work done while at Salesforce Research.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

observation x via
y = Bayes (x) == arg max P(Y = =j|x=xx x
(1)
jEy
The Bayes error is simply the probability that the Bayes classifier predicts incorrectly:
Eayes (p) == p( Bayes X)= + Y).
(2)
The Bayes classifier is optimal, in the sense it minimizes p (X) o Y) over all possible classifiers C:: Rd + )/ Therefore, the Bayes error is natural measure of 'hardness' of a particular learning task. Knowing ERayes should interest practitioners: it gives natural benchmark for the performance of any trained classifier. In particular, in the era of deep learning, where vast amounts of resources are expended to develop improved models and architectures, it of great interest to know whether it is even theoretically possible to substantially lower the test errors of state-of-the-ar models, cf. [6].
Of course, obtaining the exact Bayes error will almost always be intractable for real-world classifi- cation tasks, as it requires full knowledge of the distribution p. A variety of works have developed estimators for the Bayes error, either based on upper and/or lower bounds [2] or exploiting exact representations of the Bayes error [26, 24). Most of these bounds and/or representations are in terms of some type of distance or divergence between the class conditional distributions,
(x) == p(X = x Y = j),,
and/or the marginal label distributions т; := p(Y = j). ). For example, there are exact representations of the Bayes error in terms of a particular f --divergence [26], and in a special case in terms of the total variation distance [24]. More generally, there are lower and upper bounds known for the Bayes error in terms of the Bhattacharyya distance [2, 24], various f-divergences [20], the Henze-Penrose (HP) divergence [22, 21], as well as others. Once one has chosen a desired representation and/or bound in terms of some divergence, estimating the Bayes error reduces to the estimation of this divergence. Unfortunately, for high-dimensional datasets, this estimation is highly inefficient. For example, most estimators of f /-divergences rely on some type of e-ball approach, which requires number of samples on the order of (1/e)² e in d dimensions [26, 30J. In particular, for large benchmark image datasets used in deep learning, this approach is inadequate obtain meaningful results.
Here, we take a different approach: rather than computing an approximate Bayes error of the exact distribution (which, exact Bayes error of an approximate distribution. The basics of our approach are as follows.
argue above, is intractable in high dimensions), we propose to compute the
We show that when the class-conditional distributions are Gaussian gj (z) N Mj: E). we can efficiently compute the Bayes error using a variant of Holmes-Diaconias gration proposed in [12].
inte-
We use normalizing flows [28, 16, 9] to fit approximate distributions ú (x), by representing the original features as T(z) for Icarned invertible transformation T, where (z = N (z; μ.j Σ), for learned parameters pyy Σ.
Lastly, we prove in Proposition I that the Bayes error is invariant under invertible transfor- mation of the features, so computing the Bayes error of the approximants PÚ (x) can be done exactly by computing it for the Gaussians dj (z).
Moreover, we show that by varying the temperature of single flow model, we can obtain an entire class of distributions with varying Bayes errors. This recipe allows us to compute the Bayes error of large variety of distributions, which we use to conduct thorough empirical investigation of a benchmark datasets and SOTA models, producing a library of trained flow models in the process. By generating synthetic versions of standard benchmark datasets with known Bayes errors, and training them on SOTA deep learning architectures, we able to assess how well these models perform compared to the Bayes error, and find that in some cases they indeed achieve errors very near optimal. We then investigate our Bayes error estimates measure of objective difficulty of benchmark classification tasks, and produce a ranking of these datasets based on their approximate Bayes errors.
We should note one additional point before proceeding. In general the hardness of classification tasks can be decomposed into two relatively independent components: i) hardness caused by the lack of

---

True vs. Estimated Bayes Error
Relative Error from HDR Integration
0.4
Estimated ted True Truel/True /Tree
Mean relative
0.15
0.3
Error
0.10
0.2
0.05
0.1
Estimated
True
0.0
Temperature, T
Temperature, T
Figure 1: We compare the Bayes error estimated using HDR integration [12] with the exact error in the binary classification with equal covariance case given in (4). On the right we show the relative error from numerical integration. Shaded region on both plots shows the range over 100 runs. We see 784, and take
the integration routine gives highly accurate estimates. Here we use dimension Mi M2 to be randomly drawn unit vectors, and E I²I where T is the temperature.
samples, and ii) hardness caused by the internal data distribution p. The focus of this work is about the latter: the hardness caused by p. Indeed, even if the Bayes error of a particular task is known to be particular value Bayes it may be highly unlikely that this error achievable given model trained on only N samples from The problem of finding the minimal error achievable from given dataset of size N has been called the optimal experimental design problem [31]. While this is not the focus of the present work, an interesting direction for future work is to use our methodology to investigate the relationship between N and the SOTA-Baye error gap.
Computing the Bayes error of Gaussian conditional distributions
Throughout this section, assume the class conditional distributions are Gaussian: (x) ((2; jr Ej). In the simplest case of binary classification with K = classes, equal covariance Σ Σn = Σ, and equal marginals T2 = J. the Bayes error can be computed analytically in terms of the CDF of the standard Gaussian distribution, 4 (-)) as:
Eayes - Σ 1/2 (/2 12)l12)
(4)
When K > 2 and/or the covariances are different between classes, there is no closed-form expression for the Bayes error. Instead, we work from the following representation:
Bayes
Tk
II j
(z) (z())) pk. Ex).
(5)
R=
In the general case, the constraints (z) < (z) are quadratic, with qj (z) < (z) occurring if and only if:
(z Σ (z 11,) log det Σ, < (2 (2- p4)
14) log det Σg-
As far know, there no efficient numerical integration scheme for computing Gaussian integrals under general quadratic constraints of this form. However, we further assume the covariances are equal, E; Σ for all j I,..., K, then the constraint (6) becomes linear, of the form
aJ + byk O. where a,k: : 2E 1 (a) and by2 = n Σ Fh 11 Σ B-1... Thus expression (5) can be written
EByes Σ Tk.
II
I(a,22 bye 0)N(dz pk. E).
(8)
jzk

---

Computing integrals of this form is precisely the topic of the recent paper [12], which exploited the particular form of the linear constraints and the Gaussian distribution to develop an efficient method [7]. This method is highly
integration scheme using variant of the Golmes-Diaconiis- efficient, even in high dimensions'. In Figure we show the estimated Bayes error using this method on synthetic binary classification problem in d = 784 dimensions, where we can use closed-form expression (4) to measure the accuracy of the integration. As we can see, is highly accurate.
This method immediately allows us to investigate the behavior of large neural network models on high-dimensional synthetic datasets with class conditional distributions 43 (z) -N; 24 2). However, in the next section, will see that error of roal-world datasets as well.
use normalizing flows to estimate the Bayes
3 Normalizing flows and invariance of the Bayes error
Normalizing flows powerful technique for modeling high- nigh-dimensional distributions [28]. The main idea is to represent the random variable x as transformation Ta (parameterized by () of a vector sampled from some, usually simple, base distribution g(2; v)) (parameterized by 16), i.e.
(z)
where
((z
When the transformation T3 is invertible, change of variable formula:
obtain the exact likelihood of using standard
p(x: 0) = ((T- v) det Jr, (TT' (x)))
(10)
where 8 = (Ø, 1)) and Jr, is the Jacobian of the transformation Tg. The parameters A can be optimized, for example, using the KL divergence:
N
[()) = (x(( [(x;0)) ~
Σ
log 0 (xx), () (x.')
log det Jr, (xx) + const. (1I)
N
This approach is easily extended to the case of learning class-conditional distributions by parameter- izing multiple base distributions gj (z; vby) and computing
p 0) = - (T, (x)) det Jr, (T (x)) (x))
(12)
μ.. For example, we can take (z; Σ) N(zz; My, E), where we fit the parameters μ4j, E during training. This commonly done learn class-conditional distributions, e.g. [16]. This is the approach we take in the present work. In practice, the invertible transformation Te is parameterized as a neural network, though special care must be taken to ensure the neural network is invertible and has a tractable Jacobian determinant. Here, we use the Glow architecture [16] throughout our experiments, as detailed Section 4.
3.1 Invariance of the Bayes Error
Normalizing flow models are particularly convenient for our purposes, since we can prove the Bayes error is invariant under invertible transformation. This is formalized as follows.
Let (X,Y) Bayes error of this distribution. Let T Rd + Rd be an invertible map and denote the associated joint distribution of Z T(X) and Y. Then E (p) EBoyes (9)-
Proposition 1.
X E Rd Y = (1,..., K}, and let Enaye(() be the associated
Proof. For convenience, denote |A] as the absolute value determinant of a matrix A. Using the representation derived in [26], we can write the Bayes error as
Px(x) (x(x) pk (x)xxxx
Bayys (p)
max 0, T&
max ISSS
...
(13)
'Note that the integrals appearing in (8) are really only (K -)-dimensional integrals, since they only depend on K variables of the form aJxx x byk-

---

Then if z T(x), we have that 9& (z) = (e(((()))Jrr()) and dx = (z) dz. Hence
"i pi(x)
EByye (p)
max
0, n
max
Pk px( PI (x(x))dxx
1sisk-1
k=
9: (z)))
11
max
0, Tkk
max 1sisk-1
(2) (T)
9u (z)) (z)dz.
By the Inverse Function Theorem, Jr-1(z)] = [J) and so we get
9: (1 [T())
EByyes (p) = 11-
0,
max
9a (x
1sisk-1
9 (z) (z))
1==2
K
n qi(z)
11- TT
max
0, TK
max
9k (z)dz
15igh-1
9N (x(z)
which completes the proof.
This result means that we can compute the exact Bayes error of the approximate distributions P (x; 0) using the methods introduced in Section 2 with the Gaussian conditionals q, g,(z; M4, E). If in addition the flow model P5 (x: 0) is a good a approximation for the true class-condiiional distribution p, (x). then expect to obtain a good estimate for the true Bayes error. In what follows, we will see examples both of when this is and is not the case.
3.2 Varying the Bayes error using temperature
important aspect of the normalizing flow approach that we can in fact generate a whole family of distributions from single flow model. To do this, we can vary the lemperature of the model by multiplying the covariance Σ of the base distribution by to get (2.(2)) == N [1;; 2E). The same invertible map To induces new conditional distributions,
(x: 0) (. (x)); w))) det (To
(14)
as well the associated joint distribution p. (y x, T,P3.- 0). can easily be seen that the Bayes error of Pr is increasing in r.
Proposition 2. The Bayes error of flow models is monotonically increasing in That is, for < r', we have that (Boyes(rr) S (p.r)s(prr)..
This fact means that we can easily generate datasets of varying difficulty by changing the temperature 7. For example, in Figure 2 we show samples generated by flow model (see Section for implementation details) trained on the Mashion-MNIST dataset at various values of temperature and the associated Bayes error. As - 0+ the distribution Pj.- concentrate on the mode of the distributions p.. making the classification tasks easy. whereas when т gets large. the distributions Pj.r become more uniform, making classification more challenging. generate datasets with almost arbitrary Bayes error: for any prescribed error in the range of the map H Bayes (f-), we can numerically invert this map to find 7 for which (ay = E.
practice, this can be used to
Empirical investigation
4.1 Setup
Datasets and data preparation. We train flow models* wide variety of standard benchmark datasets: MNIST [19]. Extended MNIST (EMNIST)
[5]. Fashion MNIST [36]. CIFAR- [17], CIFAR-100 [17], SVHN [23], and KuzushijiMMIIST [4]. The EMNIST dataset has several different splits, which include splits by digits, letters, merge, class, and balanced. The images in MNIST, Fashion-MNi EMNIST, and Kuzushiji-MNIS are padded 32-by-32 pixels."
'Code can found at https://githhh.com http://gihuuh.oo/aaleesttee Sawalesoorce/Daaaarnneeeee
'Glow implementation requires the input dimension be power of 2.
5

---

(a) T=0.2, Enayes =1.11e-16
(b) 1=1.0, Eaayss =3.36o-2
(c) T=14, Eaays -1.07c-1
(d) 7=3.0, Eaayss -4.06c-1
Figure 2: Generated Fashion-MNIST Samples with Different Temperatures
We remark that we observe our Bayes error estimator runs efficiently when the input is of dimension 32-by-32-by-3, However it is in general highly memory intensive the HDR integration routine on significantly larger datasets, e.g. when the input size grows to 64-by-64-by-3 As a consequence, in our experiments we only work datasets of dimension no larger than 32-by-32-by-3.
Modeling and training. The normalizing flow model we in our experiments is pytorch implementation [13] of Glow [16]. In all our the experiments, affine coupling layers are used, the number of steps of the flow in each level K 16, the number of levels L and number of channels in hidden layers C 512.
During training, minimize the Negative Log Likelihood Loss (NLL)
NT.I((x;. = N
(logPy, (x;; 0) log Ty.).
(15)
As suggested in [16], also add classification loss predict the class labels from the second-to-last layer of the encoder with a weight of X. During the experiments we traversed configurations with X = (0.01, 0.1, 1.0, 10), and report the numbers produced by the model with the smallest NLL loss on the test set. Note here even though we add the classification loss in the objective as regularizer, the model is selected based on the smallest NLL loss in the test set instead of the classification loss or the total loss. The training and evaluation are done on a workstation with 2 NVIDIA V V00 GPUs.
4.2 Evaluating SOTA models against generated datasets

---

Synthetic MNIST
Synthetic Fashion-MNIST
0.3
Bayes Error
0.3
Bayes Error
ConvNet
WRN-28
0.2
0.2
Error
Error
0.1
0.1
0.0
0.0
0.5
1.0
1.5
2.0
0.5
1.0 1.5
Temperature, T
Temperature, T
Figure 3: Test enrors of synthetic versions of MNIST and Fashion-MNiS generated at various temperatures, and their corresponding Bayes error. Here we used 60,000 training samples, and 10,000 testing samples, to mimic the original datasets. The model used in Fashion-MNIST was a Wide-RRsNNet-28. which attains nearly start of the accuracy on the original Fashion-MNIST dataset [39]. The model used in MNIST is popular ConvNet [1].
In this section, we use our trained flow mod- els generate synthetic versions of standard benchmark datasets, for which the Bayes error is known exactly. In particular, synthetic versions of the MNIST and Fashion- MNIST datasets varying temperatures. As we saw in Section 3.2, varying the temperature allows generate datasets with different dif- ficulty. Here, we train a Wide-ResNet-288- 10
Synthetic Fashion-MNIS: MNNIS
0.4
generate
0.12
0.10
Error
0.08
0/44
model (i.e. ResNet with depth 28 and width multiple 10) [37, 35] on these datasets, and com- pare the test error to the exact Bayes error for these problems. This Wide-ResNet model (to- gether with appropriate data augmentation) at- tains nearly state-of-the-arr accuracy on the orig- inal Fashion-MNiS -NIIS dataset [39], and so we expect that our results here reflect roughly the best accuracy presently attainable on these syn- thetic datasets son fair, we use training set size of 60,000 to mimic the size of the original MNIST series of datasets.
000
Lineer
MLP
Alechiet
Boyee
Architecture
Figure 4: Errors of various model architectures (from old modern) MNIST dataset (T = 1). We can see that for this task, while accuracy has improved with modern models, there still substantial gap between the SOTA and Bayes optimal.
Synthetic Fashion-
well. To make the compari-
The Bayes errors as well as the test errors achieved by the Wide-ResNet or ConvNet models are shown in Figure As would expect, the errors of trained models increase with temperature. It can be observed that Wide-ResNet and ConvNet are able to achieve dlose-to-optimal performance when the dataset is relatively easy, e.g., gap becomes more significant when the dataset is harder, e.g. > 1.5 for MNIST and > 1 for Fashion-MNIST.
for MNIST and < 0.5 for Fashion-MNIST. The
For the Synthetic FaShion-MNIST dataset at temperature (WRN-28) considered above, we also trained three other architectures: simple linear classifier (Linear), 1-hidden layer ReLU network (MLP) with 500 hidden units, and standard AlexNet convolutional architecture [18]. The resulting test errors, well as the Bayes error, are shown Figure 4. We see that while the development modern architectures has led to substantial improvement in the test emror there is still reasonably large gap between the performance of the and Bayes optimality. Nonetheless, it is valuable know that, for this task, the Mate-offthhe-r has substantial room to be improved.
1, in addition the Wide-ResNet
SOTA
7

---

Corpus
#classes
#samples
NLL
Bayes Error
SOTA Error [29]
MNIST
I0
60,000
8.00e2
1.07e-4
1.6e-3 [3]
EMNIST (digits)
10
280,000
8.61e2
1.21e-3
5.7e-3 [27]
SVHN
10
73,257
4.65e3
7.58e-3
9.9e-3 [3]
KuzUshiji-MNISS
10
60.000
1.37e3
8.03e-3
6.6e-3 [11]
CIFAR-10
10
50,000
7,43e3
2.46e-2
3e-3
Fashion-MNIST
10
60,000
1.75e3
3.36e-2
3.09e-2 [32]
EMNIST (letters)
26
145,600
9.15e2
4.37e-2
4.12e-2 [15]
CIFAR-
100
50,000
7.48e3
4.59e-2
3.92e-2 [10]
EMNIST (balanced)
47
131,600
9,45e2
9,47e-2
8.95e-2 [15]
EMNIST (bymerge)
47
814,255
8,53e2
1.00e-1
1.90e- [5]
EMNIST (byclass)
62
814,255
8.76e2
1.64e-1
2.40e-1 [5]
Table I: We evaluate the estimated Bayes error on image data sets and rank them by relative difficulty. Comparisons with prediction performance of state-of-the-arr neural network models shows that our estimation is highly aligned with empirically observed performance.
4.3 Dataset Hardness Evaluation
important application our Bayes error estimator estimate the inherent hardness of a given dataset, regardless of model. We run our estimator several popular image classification corpora and rank them based on our estimated Bayes error. The results are shown in Table 1. As a comparison also put the SOTA numbers in the table.
Before proceeding, make two remarks. First, all of the Bayes errors reported here were computed using temperature т = 1. This is for two main reasons: 1) setting r = reflects the flow model attaining the lowest testing NLL., and hence is in some sense the "best" approximation for the true distribution, 2) in our experiments, the ordering of the hardness of classes is unchanged by varying temperature, and taking
is reasonable default. Second, the reliability of the Bayes errors reported here as a measure of inherent difficulty are dependent on the quality of the approximate distribution p; if this distribution is an adequate estimate of the distribution p, then it is possible that the Bayes errors do not accurately reflect the true difficulty of the original dataset. Therefore, we also report the NLL for each model as a metric evaluate the quality of the approximant p.
First, we observe that, by and large, the estimated Bayes errors align well with SOTA. In particular, if we constrain the NLL loss to smaller than 1000, then ranking by our estimated Bayes error aligns exactly with SOTA.
Second, the NLL loss in MNIST, Fashion MNIST, EMNIST and Kuzushiji-MNIST is relatively low, suggesting good approximation by normalizing flow. However corpora such as CIFAR- 10, CIFAR-100, and SVHN may suffer from lack of training samples. In general large NLL loss may be due to either insufficient model capacity or lack of samples. our experiments, we always observe the Glow model is able to attain essentially zero error the training corpus, so it is highly possible the large NLL loss is caused by the lack of training samples.
Third, for datasets such as MNIST, EMNIST (digits. letters, balanced), SVHN, MaShIOn-MNISTT, KUNIS, CIFAR-I0, and CIFAR-I00 the SOTA numbers are roughly the same order of magnitude as the Bayes error. On the other hand, for EMNIST (bymerge and byclass) there is still substantial gap between the SOTA and estimated Bayes errors. This is consistent with the fact that there is little published literature about these two datasets; as a result models for them are not as well-developed.
Limitations, Societal Impact, and Conclusion
In this work, we have proposed new approach to benchmarking state-of ffite--f-the-an models. Rather than comparing trained models to each other, our approach leverages normalizing flows and a key invariance result to be able to generate benchmark datasets closely mimicking standard benchmark datasets, but with exactly controlled Bayes error. This allows us to evaluate the performance of trained models absolute, rather than relative, scale. In addition, our approach naturally gives us

---

method to assess the relative hardness of classification tasks, by comparing their estimated Bayes errors.
While our work has led to several interesting insights, there are also several limitations at present that may be fruitful source of future research. For one, it is possible that the Glow models we employ here could be replaced with higher quality flow models, which would perhaps lead to better benchmarks and better estimates of the hardness of classification tasks. To this end, it possible that label noise in standard datasets contributes to our inability to learn higher-quality flow models [25]. To the best of our knowledge, there has not been significant work using normalizing flows to accurately estimate conditinnn distributions for NLP datasets; this in itself would be an interesting direction for work. Second, a major limitation of our approach that there isn an immediately obvious way to assess how well the Bayes error of the approximate distribution Bayes (p) estimates the true Bayes error Bayes (p). Theoretical results which bound the distance between these two quantities, perhaps in terms of divergence D(pll)), would be of great interest here.
the well-document
As detailed in [34], there may be pernicious impacts of the common task framework and the so-called Holy Grail performativity that it induces, For example, singular focus by the community on the leaderboard performance metrics without regard for any other performance criteria such as fairness or respect for human autonomy. The work here may or may not exacerbate this problem, since trying to approach fundamental Bayes limits is psychologically different than trying to do better than SOTA. As detailed in [33], the shift from competing against others to pursuit for the fundamental limits of nature may encourage wider and more diverse group of people participate in ML research, e.g. those with personality type that has less orientation to competition. It is still to be investigated how to do this, but the ability to generate infinite data of a given target difficulty (yet style of existing datasets) may be used to improve the robustness of classifiers and perhaps decrease spurious correlations.
References
[1] Baxic MNIST http:////ttgttt...c.o//////////s Accessed: 2021 -05-008
[2] Visar Berisha et al. "Empirically Estimable Classification Bounds Based on a Nonparametric Divergence
Measure". In: IEEE Transactions on Signal Processing 64.3 (Feb. 2016), pp. 580-591. DOT: 10. 1109/
TSP. 2015.2200 2477805.
[3] Adam Byerly, Tatiana Kalganova, and Ian Dear. A Branching and Merging Convolutional Network with Homogeneous Filter Capsules. arXiv:2001.00 109 [es.CV]. Jan. 2020.
[4] Tarin Clanuwat et al. Deep Learning for Classical Japanese Literature. Dec. 3, 2018. arXiv: cs CV/
1912. 1812.01718 css. CV
[5] Gregory Cohen et al. "EMNIST: An extension of MNIST to handwritten letters". In: Proceedings of the 2017 International Joint Conference on Neural Networks (IJCNN.. May 2017, pp. 2921-2926. DOE:
10. 11 11/NNCCNN... 2.0 17, 7. 7966217. 7
[6] Daniel J. Costello Jr. and G. David Forney Jr. "Channel coding: The road to channel capacity". In: Proceedings of the IEFE 95.6 (June 2007), pp. 1150-1177. DOI: 10. 1109 JPRRCC. 2007 8888851888 88.
[7] Persi Diaconis and Susan Holmes. "Three Examples of Monte-Carlo Markov Chains: At the Interface Between Statistical Computing, Computer Science, and Statistical Mechanics". In: Discrete Probability and Algorithms. Ed. by David Aldous et al. New York, NY: Springer, 1995, pp. 43-56.
[8] David Donoho. "Comments on Michael Jordan's 's Essay "The AI Revolution Hasn't 't Happened Yet"". In: Harvard Data Science Review (June 2019). DOE: 0 11 62/ 608 192 c 6698b.7.
[9] Ethan Fetaya et al. "Understanding the Limitations of Conditional Generative Models". In: Proceedings of the International Conference on Learning Representations (ICLR). Apr. 2020.
[10] Pierre Foret et al. "Sharpness-aware Minimization for Efficiently Improving Generalization". In: Pro- ceedings of the International Conference Learning Representations (ICLR). May 2021. URL: https:
I ooppnnreiiie lew. net/ / f rum? ? (d-6Tmmmppp lrM.
[11] Xavier Gastaldi. "Shake-Shake regularization". In: CoRR abs/1 705.07485 (2017). aivi:: 1705. 07485.
URL: http: //axiv org / abs / 17005. 07485.
[12] Alexandra Gessmer, Oindrila Kanjilal, and Philipp "ennig.""ntegrene "Integrals over Gaussians under Lincar Domain Constraints". In: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS). Aug. 2020, pp. 2764-2774.
[13] Glow in PyTorch. ht attps:: / /githubb. con/ chrischuter goow. Accessed: 2021-05-08.
[14] Tin Kam Ho and Mitra Basu. "Complexity Measures of Supervised Classification Problems". In: IEEE Transactions on Pattern Analysis and Machine Intelligence 24.3 (Mar. 2002), pp. DOI: 10.
1109/3 34.9/34.00 990132.

---

[15] Hussain Mohammed Dipu Kabir et al. SpinulNet: Deep Nearal Network with Gradual Input. arXiv:2007. NIV:2007.033477 [es.CV]. Sept. 2020.
[16] Diederik P. Kingma and Prafulla Dhariwal. "Glow: Generative Flow with Invertible 1 x 1 Convolutions".
In: Advances in Neural Information Processing Systems 31. Fd. by S. Bengio et al. Curran Associates, Inc., 2018, pp. 10215-10224. URL: https : prwceedings neurips ea paper 2018
file/d139db
[17]
Alex Krizhevsky. Learning Mulriple Layers of Features from Tiny Images. Tech, rep. Apr. 2009. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. "Imagenet classification with deep convolutional neural networks". In: Advances in neural information processing systems 25 (2012), pp. 1097-1106
[18]
[19]
Yann LeCun et al. "Gradient-Basse" Learning Applied to Document Recognition", In: Proceedings of the JEEE 86.11 (Nov. 1998), pp. 2278-2324. DOL: 10. 1109/5.0111..1 72699/577777999 726791.
[20] Kevin R. Moon and Alfred O. Hero III. "Multivariate f-divergence Estimation With Confidence", In: Advances in Neural Information Processing Systems 27. Ed. by Z. Ghahramani et al. Curran Associates, Inc., 2014, pp. 2428. URL: ht ppwpeediiiggg....m neurips......... wttpppppe//1//////////pp //file/ www.diiinnnnnnn.inn.....m Paaeee
[21] Kevin R. Moon, Alfred O. Hero II, and Véronique Delouille. "Meta learning of bounds the Bayes classifier error". In: Proceedings of the 2015 IEEE Signal Processing and Signal Processing Education Workshop (SP/SPE). Aug. 2015, pp. 13-18. DOT: 10. 1109 /SSS-SSPPPP
73 7355200.
[22] Kevin R. Moon et al. "Ensemble Estimation of Information Divergence". In: Entropy 20.8 (2018), p. 560. DOI: 10. 03390/2200005
[23]
Yuval Netzer et al. "Reading Digits in Natural Images with Unsupervised Feature Learning.. In: NIPS Workshop on Deep Learning and Unsupervised Feature Learning. Dec. 2011.
[24] Frank Nielsen. "Generalized Bhattacharyya and Chernoff upper bounds on Bayes error using quasi- arithmetic means". ". In: Pattern Recognition Letters 42 (June 2014), pp. 25-34. DOL: 10. 1016/5
patrec. 2etrre.20144 2.44.01. .1.001.002..000000000 002.
[25] Curtis G. Northcutt, Anish Athalye, and Jonas Mueller. Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks, arXiv:2103.1443 [st) Mar. 2021.
[26] Morteza Noshad, Li Xu, and Alfred Hero. Learning to Benchmark: Determining Best Achievable Mis- classification Error from Training Data. a1Xiv:1909.077
[stat.ML]. Sept. 2019.
[27] Pedram Pad et al. "Efficient Neural Vision Systems Based Convolutional Image Acquisition". In: Proceedings of the IEEF//VF Conference on Computer Vision and Pattern Recognition (CVPR). June 2020. pp. 12285-12294.
[28] George Papamakarios et al. "Normalizing Flows for Probabilistic Modeling and Inference". In: Journal of Machine Learning Research 22.57 (2021), pp. 1-64.
[29] Puper With Code for Image Classification Dutasets. https: : pestps://papeee http://ppppssttttheeeee com/ task/ image-cll caage-cllassio cosssficaiion Accessed: 2021 -05-08.
[30] Barnabás P6czos, Liang Xiong, and Jeff Schneider. "Nonparametric Divergence Estimation with Appli- cations to Machine Learning on Distributions". In: Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence (UAI'II). July 2011, pp. 599-608.
[31] K. Ritter, Average-Can Analysis of Numerical Problems. Average-case Analysis of Numerical Problems no. 1733. Springer, 2000. ISBN: 9783540674498. URL:: https: /books..k..... googl e. ccm/books id=mP 2MoOzXénIC.
[32] Muhammad Suhaib Tanveer. Muhammad Umar Karim Khan, and Chong-Min Kyung. "Fine- Funing DARTS for Image Classification". In: Proceedings of the 25th International Conference on Pattern Recognition (ICPR). Jan. 2021, pp. 4789-4796. DOE: 10. 1 CCR48886 2022 922221.
[33] Lav R. Varshney. "Addressing Difference in Orientation toward Competition by Bringing Fundamental Limits to AI Challenges". In: NewrIPS workshop, ML Competitions at the Grassroots (CiML 2020). Dec. 2020.
[34] Lav R. Varshney, Nitish Shirish Keskar, and Richard Socher. Pretrained Al Models: Performativity, Mobility, and Change. arXiv:1909.03290 [cs.CY]. Sept. 2019.
[35] WideResnet in PyTorch. https: / github. com / mel melimelkettt iketoy////// / wide - resnet pyttorh. Accessed: 2021-05-08
[36] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: A Novel Image Dataset for Benchmarking Machine Learning Algorithms. 1rXiv:1708.077 [cs.LG]. Sept. 2017.
[37] Sergey Zagoruyko and Nikos Komodakis. "Wide Residual Networks". In: Proceedings of the British Machine Vision Conference (BMVC). Ed. by Richard C. Wilson, Edwin R. Hancock, and William A. P. Smith. Sept. 2016, pp. 87.1-87.12.
[38] Peiliang Zhang al. "DIME: An Information- Theorettc Difficulty Measure for AI Datasets". In: NeurIPS
2020 Workshop DI. Blind Submission. Dec. 2020.
10

---

[39] Zhun Zhong et al. "Random Erasing Data Augmentation". In: Proceedings of the AAAI Conference on
Artificial Intelligence 34.07 (Apr. 2020), pp- 13001-13008. DOI: 10. 1609/aaa3 htt.///aaa...100....... w34.07.71000000
URL: wwwpshttp//....... / aaai, wwwp/rrww....oooot..otoo.teoeeee phpp///ppppppppppppppppppp////pp wtt.a///aaaieeeeee////////


Reviews:
[{"review_id": "sUw65d7V0M", "reviewer": "Reviewer_Vaq4", "summary": "This paper focuses on computing the exact Bayes error of generative models learned using normalizing flows.\n\nThe main contributions are:\n1. The paper proposes to compute the exact Bayes error of an approximate distribution instead of computing an approximate Bayes error of the exact distribution.\n2. The paper shows that by varying the temperature of a single flow model, they can obtain an entire class of distributions with varying Bayes errors.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes a novel method to design benchmarks for classifiers, where Bayes errors can be efficiently calculated. The method consists of two steps: (1) Approximate the distribution of a given data set by a normalizing flow with the input distributed according to GMM. (2) The Bayes error of the data set generated by the normalizing flow can then be calculated by the Holmes-Diaconis-Ross integration.\n\nThe conclusion given by Proposition 1 is very interesting for readers, and is possibly useful for further research on normalizing flows. However, the overall significance is marginal. The major limitation of the benchmarks produced by generative models (including NFs) is: The structure of the generative model will introduce some implicit bias, and the classifier using the same transformations (like convolution operators) could be better than the others.\n\nAfter rebuttal: First, I disagree with authors that \"the same order of magnitude as the error of the same architectures on the original datasets seems to indicate that this is not a substantial issue in practice\". For common data sets, the error rates of popular deep learning classifiers are all in the same order of magnitude. Second, I agree with reviewer Q5Ht that better NLL might not lead to better estimates of the Bayes error, especially for normalizing flows. So I do not change my evaluation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "drXUqaZS_zT", "reviewer": "Reviewer_TyQJ", "summary": "In this paper, the authors went on a series of steps to measure how close to theoretical optimal are current deep learning algorithms. They first obtain the optimal misclassification Bayes error under the assumption that features follow a Gaussian distribution conditioned on the j-th class. Next, they fit approximate distributions \\hat{p}_j(x) where x=T(z) and T is an invertible transformation and z is Gaussian. Finally, they show (but the proof is missing) that the Bayes error is invariant under invertible transformations. Putting these building blocks creatively together we have the results about the quality of the current deep learning classification methods. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading this paper. In my opinion, they use in an ingenious way known results (such as the Holmes-Diaconis-Ross integration method) to obtain an answer to an important question: just how close to the theoretical optimal Bayer rule misclassification rule are the state-of-art (SOTA) deep learning classification algorithms? Given the ever-present fear of being unknowingly trapped on local minima, far away from the global minimum, discovering that some SOTA algorithms come close to the best possible is reassuring. Indeed, there is a strong linear relationship between the Bayes error and the SOTA error shown in the last two columns of Table 1. A scatterplot of these two columns shows more clearly the discrepancy of the points corresponding to the EMNIST by merge and EMNIST by class datasets from the linear trend produced by the other datasets. \n\nThe paper is not hard to read. It is very well written and it goes on theory in the right depth needed for the ideas discussed in the paper. I was not familiar with the Holmes-Diaconis-Ross method and found that the authors made creative use of this result. Also, it was nice to know about the invariance of the Bayes error under invertible transformations, even non-linear ones. Unfortutenaly, the proof is in Appendix A which has not been provided. At least, I could not find it on the OpenReview website. \n\nIn addition to the points raised by the authors in section 5, I can think of two other points: (1) it would be worthwhile deriving better measures than simply the NLL to measure the discrepancy between p and p-hat. (2) is it possible to expand the methods of this paper by focusing on other performance metrics different from the expected misclassification error? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The  authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "ODjMc_h84y", "reviewer": "Reviewer_Q5Ht", "summary": "this paper proposes a simple way to estimate the bayes error of a classification dataset; fit a invertible generative model to the dataset, and use Gaussians in the latent space of the flow model. Since the bayes error is invariant to invertible transformations, the Bayes error can be estimated in the latent space through integration techniques. This is performed for a few real world datasets to investigate how close we are to reaching the Bayes error. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "After rebuttal: I've made my score slightly higher as the authors convinced me regarding point 1 of my review. However, regarding point 2, I am still not convinced. The argument about convergence of the distribution does not really help in any way; as we cannot really say whether the flow models are converging in any sense. What would really convince me is some example that shows that a better NLL implies a better Bayes error estimate (as the NLL is at least optimized by the flow models). However, as my counterexample suggests, this may be difficult to achieve and may requite further additional assumptions. Unless this is offered, or some other experimental results that show that better NLL really leads to better estimates of the Bayes error, I could further improve my score - as of now, it remains unclear to me whether better flow models really result in better Bayes error estimates, which seem to me one of the essential assumptions of this work. \n\nRegarding 4; I think I was confused with Variational Auto-Encoders; I will check this further in more detail... Maybe it does not apply to flow models at all. Regarding remark 7; what maybe I didn't write clearly, is why is this remark ever made in the paper? It seems completely off-topic to me, which is what confuse me most.  \n\nI like the paper, but issues 1-5 are problematic for it's acceptance in my eyes. Some statements about computational feasibibility seem contradicting to me or unconvincing. The same goes for the quality of the estimator. Here I think even it is possible to construct examples that contradict the statements in the paper. Finally, there are a few details regarding the experimental setup that are either wrong or incorrect or not carefully described enough. \n\nBelow some information that hopefully could help improve the work. \n\nMost problematic issues:\n1) Claims regarding computational efficiency are not precise enough, too vague and contradictory\n\n\"This method is highly  efficient, even in high dimensions.\" (line 99)\nseems to contradict statement in line 166-169. \n\"We remark that we observe our Bayes error estimator runs efficiently when the input is of dimension\n167 32-by-32-by-3. However it is in general highly memory intensive to run the HDR integration routine\n168 on significantly larger datasets, e.g. when the input size grows to 64-by-64-by-3. As a consequence,\n169 in our experiments we only work on datasets of dimension no larger than 32-by-32-by-3.\"\n\nInstead, it would be better if you can give the big O notation complexity. If this is infeasible or not sensible, I think it would be worthwhile to include a graph of computation time + memory used versus  dimensionality, so at least we can judge whether it is really computational feasible. \n\n\n2) Claims regarding the accuracy of the estimator are too vague \n\n\"As we can see, it is highly accurate.\" (line 102). \n\nThis claim is already very difficult to judge. From the figure I cannot see how large the errors are. Please include a table with some numbers (MSE, MAE) so we can judge the size of the errors. It would be good to include the Monte-Carlo baseline (described in 4.4) estimator here, so we can judge whether errors are really small of this estimator. Would be good to mention something about their trade-offs (when to use Monte-Carlo, when to use this integration technique). \n\n\"If in addition the flow model\nis a good a approximation for the true class-conditional distribution\nthen we expect to obtain a good estimate for the true Bayes error.\" (line 134)\n\nI think this claim is too strong. I would even go in the opposite direction, I think we can quite easily make an example where for example the log likelyhood or other density estimation metric is very 'good' (e.g. small NLL), while the bayes estimator is very poor, and vice versa. \n\nFor example, take \nP_+ = N(0,1), P_- = N(2,1)\nQ_+ = N(0,1), Q_- = N(3,1)\nR_+ = U(0,1), R_- = U(a,1+a)\nwhere I used N as notation for the normal distribution N(mu, sigma) and U(c1,c2) as the uniform distribution on the interval [c1,c2]\n\nI for sure can find a value a such that R has the exact same bayes error as P. However, in many density estimation metrics R would be a worse approximation of P than Q. This is also in line with \"A note on the evaluation of generative models\" who find that good performance in one metric generally doesn't lead to good performance in another, for tasks related to density estimation. \n\nThis to me suggests that a good likelyhood model or a good density estimation metric is definitely not sufficient to get a good estimate of the Bayes error. \n\nAs a starter to investigate this, I suggest the authors investigate the synthetic task of Section 2, varying the NLL of the density model versus the error of the estimator. I would not be surprised if the behavior can be non-monotonic. Of course, it is also highly dependent on how the models are obtained in such a small experiment. As two obvious approaches I would consider: 1) taking models from all epochs to get to a series of density models 2) randomly initialising all weights of the model many times \n\nOther problems\n\n3) lines 175-181. I'm confused, what is now tuned using which splits?? Generally, we cannot tune a parameter using the test set, in that case all the performance metrics on the test set are not thrustworthy anmore! So maybe all the NLL's need to be updated?\n\n4) How is the NLL computed? MNIST is inherently a discrete dataset, while the flow model is continuous. This should be clarified. See also \"A note on the evaluation of generative models\". \n\n5) I couldn't find how the \\mu's were set for all datasets. I think it could be nice to look at the confusion matrices that we can obtain by models trained on the synthetic datasets, and compare those with confusion matrices on the real datasets. This could maybe give a good idea how to put the \\mu's in the latent space to give a more realistic approximation of the true distribution. \n\nOther minor remarks\n\n6) \"components: i) hardness caused by the lack of\nsamples, and ii) hardness caused by the internal data distribution p. \" line 76). \nThis in literature is called also the estimation error versus the irreduceable error. Maybe good to cite a text book or chapter from \n\"Understanding Machine Learning: From Theory to Algorithms\" for example?\n\n7) \"The problem of finding the minimal error achievable from a given dataset of size has N been called the optimal experimental design problem [17].\n\" line 80.\n\nThe wording is very confusing here. Trying to find a model with minimal error is typically called machine learning, in general. The authors seem to talk about active learning, where the points (x,y) can be chosen by an active learning algorithm. This latter is indeed called optimal experimental design.\n\n8) line 223. I think the best argument is that all flow models are trained with \\tau = 1, and the \\tau is changed only after the training, right? This makes \\tau = 1 the logical choice. However: I think it MAY be possible that another \\tau may actually offer the best fit on the validation data! Especially if the models are overfitted. Maybe this makes even more sense, to tune \\tau on validation data? \n\n9) line 239. Zero error? Are we talking NLL or classification loss?\n\n10) Figure 2: maybe say something about \\tau >= 1.4; that these samples do not seem realistic anymore? \n\n11) Other more interesting experiments could be created by varying the amount of training samples from the synthetic datasets, instead of keeping this number fixed. \n\n12) Of course, the golden standard to determine the Bayes error could be by doing a large scale experiment where people actually label the datasets. This could be an interesting way to check the reliability of the estimates. But maybe this was already done for MNIST for example? \n\n13) I think that the proof of proposition 1 can be much simplified, by using a proof by contradiction and using simple invertibility of the mapping. Or maybe I'm simplifying the problem too much.... For a discrete input space I think this should definitely work, but maybe for a continuous space there are some problems with this technique that I cannot foresee now. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "For limitations see above. Regarding societal impact I see no problems. ", "review_text": "", "extra_scores": {"ethical_concerns": "I see no issues. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "BsE_RxniTFo", "reviewer": "Reviewer_8UYK", "summary": "The paper introduces a new method to estimate the Bayes error for multi-class classification problems with complex feature spaces. The central idea is to estimate for each class a density model based on normalizing flows, and use the estimated densities to compute the Bayes error approximately. The authors present two theoretical results that intend to illustrate that normalizing flows are well suited for this problem. A first theoretical result shows that the Bayes error is invariant under an invertible linear transformation of the raw features, which is typical in normalizing flows. A second theoretical result states that the Bayes error of normalizing flows is monotonically increasing w.r.t. the temperature parameter pi. \n\nIn addition, two types of experimental results are reported. In a first experiment, synthetic data is generated, starting from the Fashion MNIST dataset, and using flow-based models as the ground truth (i.e. the underlying distribution on population level). It is shown that on this data the performance of SOTA neural networks still shows a gap with the Bayes error, confirming that such models don't estimate the Bayes error yet. In a second type of experiments, flow-based models are fitted on classical image classification benchmarks. It is shown that the estimated Bayes error aligns well with the error of SOTA models in the sense that similar rankings of datasets are obtained.    ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think that this is an interesting paper and I enjoyed reading it. The paper is very well written and easy to follow. As far as I know the proposed methodology is novel, and the presented method is simple yet appealing. The two theoretical results (Proposition 1 and 2) have an added value for the paper. Estimating the Bayes error is also a practically relevant problem, so this paper scores good on the criteria originality, quality, clarity and significance. \n\nThe experimental results are also interesting, but the experimental setup is different from what I expected to read. The authors don't compare their approach to other methods that intend to estimate the Bayes error. I understand that such a comparison is not easy, because the Bayes error is not known for real datasets. However, at least some methods could be compared on synthetic data (I refer to synthetic data that is generated according to a different model than the Glow model, unlike the synthetic data in Section 4.2). In fact there are many baselines that could be tested. The authors argue that divergence-based methods, such as references 7 to 11, don't scale well to high-dimensional data, but there is a recent divergence-based method that is also used on MNIST: https://arxiv.org/pdf/1811.06419.pdf. The authors don't seem to know that work. \n\nIn addition, estimating the Bayes error is very related to uncertainty quantification, which has received a lot of attention recently in the machine learning community. Many simple baselines could be tested. For example, it is very common in deep learning research for uncertainty quantification to first fit a softmax network, followed by density estimation in the penultimate layer. In this scenario, classical density estimation methods can be used, such as linear discriminant analysis, Gaussian mixtures, kernel density estimation, etc. -- see e.g. Lee et al. \"A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks\" Neurips 2018. In addition, other types of deep generative models such as autoregressive models and autoencoders are also useful baselines -- see e.g. Nalisnick et al. \"Do deep generative models know what they don't know?\" ICLR 2019.  I would be interested to see how normalizing flows perform w.r.t. such baselines. At least the work of Nalisnick reports some negative results for flow-based models. \n\nFor the experiment in Section 4.2 it is interesting to see that SOTA methods don't come close to the Bayes error. From this it might be concluded that these methods are not good in estimating the Bayes error, but it might also be the case that the error of those methods can be reduced by making architectural changes. It is not unlikely that existing SOTA methods are optimized for classical benchmarks, while having suboptimal architectures for the synthetic data of the authors. \n\nFor the experiment in Section 4.3 it is counterintuitive that for some datasets the estimated Bayes error is lower than the error of SOTA methods. This is of course because the method of the authors only provides an estimate of the Bayes error. In uncertainty quantification for classification models, aleatoric uncertainty corresponds exactly to the Bayes error.  In the introduction, the authors motivate that in their work they only want to focus on this uncertainty component, and not on the epistemic uncertainty component. However, I don't believe that this component can be ignored. Fitting a density model is an estimation process, which leads to epistemic uncertainty. So, this work is very related to papers on uncertainty quantification, where often a distinction between aleatoric and epistemic uncertainty is made.  I believe that the authors ignore that literature too much. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above. ", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: From the reviews and the discussion, a consensus emerges that the paper contains a valuable contribution, but some claims need more precision and require more throughout empirical comparison. These issues need to be addressed by a proper revision, and would require another round of reviewing.
Decision: Accept (Poster)