BOLT: Universal Classifier Training via a Bayes-Error Upper Bound

Mohammadreza Tavasoli Naeini; Ali Bereyhi; Morteza Noshad; Ben Liang; Alfred O. Hero

cs.LGJan 13, 2025

BOLT: Universal Classifier Training via a Bayes-Error Upper Bound

Authors: Mohammadreza Tavasoli Naeini, Ali Bereyhi, Morteza Noshad, Ben Liang, Alfred O. Hero

Organizations: University of Michigan · University of Toronto · Stanford University

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.

Figures & tables

Panel of Figure 1 — Fig. 1: Analytic BER and BOLT test classification error versus class-mean separation, with 20,000 training samples and 1000 test samples.

Panel of Figure 2 — Fig. 2: Classifier errors and the $\varepsilon$ -ball Bayes-error estimate versus training-set size for the four-class task in a $d=20$ -dimensional space.

Method	CIFAR-10	MNIST	F-MNIST	IMDb	SST-2
LDA	42.0	87.9	80.4	86.8	–
RF	48.0	95.6	88.0	80.3	–
CE	91.9	99.3	91.6	91.8	89.9
BOLT	93.3	99.5	92.6	92.8	91.3

TABLE I: Classification accuracy (%) for image-classification and binary sentiment-analysis tasks with BOLT and CE. Neural entries correspond to the final epochs shown in Figure 3 , except SST-2, which uses its stated three-epoch run.

Dataset	Method	FLOPs/image (G)	Time/epoch (s)	Executed epochs	Total time (s)
CIFAR-10	ResNet-18 + CE	0.041	12.0	100	$\approx 1200$
CIFAR-10	ResNet-18 + BOLT	0.041	13.0	100	$\approx 1300$
MNIST	CNN + CE	–	3.6	20	$\approx 72$
MNIST	CNN + BOLT	–	4.0	20	$\approx 80$
MNIST	$\varepsilon$ -ball	–	–	one shot	210

TABLE II: Computational cost for the CIFAR-10 and MNIST experiments. Total neural-network times are approximate because they are calculated from rounded per-epoch measurements.

Checkpoint	Sparsity (%)	BOLT (%)	CE (%)
Epoch 10	20.0	85.23	91.29
Epoch 50	48.8	92.74	92.47

TABLE III: Fashion-MNIST pruning results at the first retained post-pruning checkpoint and the final pruning-and-fine-tuning checkpoint.

Panel of Figure 6 — Fig. 4: $t$ -SNE visualizations of MNIST test embeddings learned by the CNN with CE and BOLT after 10 epochs.

Multiclass Classification

Multiclass classification assigns inputs to one of several labels while addressing uncertainty, class imbalance, and errors across classes.

See all 95 papers

Classification with Abstention Under Class-Conditional Error Constraints
Sep 18, 2026Mohammadreza M. Kalan, Yuyang Deng, Sanaz HamidiBinary Classification Selective Prediction
Univ Rennes, Ensai, CNRS, CREST–UMR 9194, F-35000 Rennes, France · Columbia University, Department of Statistics
Distributional Loss for Robust Classification
Jun 11, 2026Kathleen Anderson, Thomas MartinetzRobust Loss Functions Classification
Institute for Neuro- and Bioinformatics, University of Lübeck, Germany
Realizable Bayes-Consistency for General Metric Losses
May 5, 2026Dan Tsir Cohen, Steve Hanneke, Aryeh KontorovichStatistical Learning Theory
1Ben-Gurion University of the Negev · 2Purdue University, USA.

Sep 18, 2026J/K move · Enter open · S save

Classification with Abstention Under Class-Conditional Error Constraints

Mohammadreza M. Kalan, Yuyang Deng, Sanaz Hamidi

Univ Rennes, Ensai, CNRS, CREST–UMR 9194, F-35000 Rennes, France · Columbia University, Department of Statistics

Binary Classification Selective Prediction Statistical Learning Theory Minimax Estimation

Open paper AskPDF arXiv

We study binary classification with abstention under separate class-conditional error constraints, with the objective of minimizing abstention while keeping both errors below prescribed thresholds. We characterize the distribution-free minimax rate of excess abstention risk, up to logarithmic factors, in terms of the complexity of the hypothesis class and the sample size. To make the framework amenable to computation with models such as neural networks, we introduce surrogate-loss formulations and derive finite-sample guarantees for excess surrogate ambiguity risk. We formulate the resulting learning task as a constrained optimization problem and characterize its computational complexity in the convex setting. Finally, we evaluate our approach on various datasets and compare its performance with a competing method for this problem.

Abstract

Multiclass Classification

Explore similar work

Classification with Abstention Under Class-Conditional Error Constraints

Distributional Loss for Robust Classification

Realizable Bayes-Consistency for General Metric Losses