arXiv:2501.07754v2 Announce Type: replace-cross Abstract: This work introduces a novel approach to compute a universal upper bound on the Bayes error rate (BER) from classifier-output samples, which serves as a Bayes-error-related performance criterion for the underlying classification task. We show that the bound is tight in the binary case and characterize the max-sum gap that appears in the aggregate multiclass formulation. Based on this bound, we define a new loss function, called Bayes optimal learning threshold (BOLT), for training parameterized classifiers. For each data sample, the BOLT loss computes a term whose expectation upper-bounds the Bayes error, so that during training the model parameters can be updated toward minimizing this bound. Numerical experiments with both synthetic and real-world datasets show that, in the reported settings, BOLT training often attains lower held-out classification error than cross-entropy training.