# Learning to Bound the Multi-class Bayes Error

arXiv: https://arxiv.org/abs/1811.06419 · HTML: https://mlsanity.com/paper/1811.06419/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2018.

## Built on by (most cited first, 9 of 9)

- [Is the Performance of My Deep Network Too Good to Be True? A Direct Approach to Estimating the Bayes Error in Binary Classification](https://mlsanity.com/paper/2202.00395/) (2022)
- [Evaluating Bayes Error Estimators on Real-World Datasets with FeeBee](https://mlsanity.com/paper/2108.13034/) (2021)
- [Certified Robust Accuracy of Neural Networks Are Bounded due to Bayes Errors](https://mlsanity.com/paper/2405.11547/) (2024)
- [How Does Bayes Error Limit Probabilistic Robust Accuracy](https://mlsanity.com/paper/2405.14923/) (2024)
- [Bayes Error Rate Estimation in Difficult Situations](https://mlsanity.com/paper/2506.03159/) (2025)
- [Revisiting GAN with Bayes-Optimal Discrimination](https://mlsanity.com/paper/2510.25609/) (2025)
- [Towards Provably Unlearnable Examples via Bayes Error Optimisation](https://mlsanity.com/paper/2511.08191/) (2025)
- [The Calibration Channel Determines the Bayes-Error Proxy: An Exact Law for Temperature-Induced Distortion](https://mlsanity.com/paper/2607.18162/) (2026)
- [BER-PEF: Unified Human Mobility Predictability Evaluation via Bayes Error Rate Estimation](https://mlsanity.com/paper/2609.04292/) (2026)

## Abstract (arXiv)

In the context of supervised learning, meta learning uses features, metadata and other information to learn about the difficulty, behavior, or composition of the problem. Using this knowledge can be useful to contextualize classifier results or allow for targeted decisions about future data sampling. In this paper, we are specifically interested in learning the Bayes error rate (BER) based on a labeled data sample. Providing a tight bound on the BER that is also feasible to estimate has been a challenge. Previous work[1] has shown that a pairwise bound based on the sum of Henze-Penrose (HP) divergence over label pairs can be directly estimated using a sum of Friedman-Rafsky (FR) multivariate run test statistics. However, in situations in which the dataset and number of classes are large, this bound is computationally infeasible to calculate and may not be tight. Other multi-class bounds also suffer from computationally complex estimation procedures. In this paper, we present a generalized HP divergence measure that allows us to estimate the Bayes error rate with log-linear computation. We prove that the proposed bound is tighter than both the pairwise method and a bound proposed by Lin [2]. We also empirically show that these bounds are close to the BER. We illustrate the proposed method on the MNIST dataset, and show its utility for the evaluation of feature reduction strategies. We further demonstrate an approach for evaluation of deep learning architectures using the proposed bounds.