PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayes-Optimal BER and AUC: Estimation and Evaluation of Estimators

Ryota Ushio, Takashi Ishida, Masashi Sugiyama

arXiv:2609.02304v1cs.LGstat.ML

TL;DR

The paper addresses the lack of estimators for Bayes-optimal BER and AUC, metrics suited to class imbalance and label noise. It develops soft-label-based estimators for clean and corrupted observations, then extends FeeBee to evaluate them when optima are unobservable; experiments validate both components.

  • Problem

    Estimating Bayes-optimal BER and AUC remains underexplored, despite their practical importance under class imbalance and label noise.

  • Method

    The paper develops soft-label-based estimators for clean and corrupted labels and extends FeeBee with noise-injection-based evaluation scores for optimal BER and AUC.

  • Results

    Experiments on synthetic and real-world datasets validate the proposed estimators and evaluation procedure.

  • Takeaways & Limitations

    Optimal BER and AUC estimators can be evaluated on real-world datasets without knowing the true optima, using a procedure applicable to any such estimator.

  • Takeaways & Limitations

    The corruption model is simple and does not cover arbitrary instance-dependent corruption.

Abstract

from arXiv · show

A fundamental quantity in machine learning is the optimal performance achievable by any model on a given task. Estimating this quantity allows us to distinguish the irreducible part of the error from a deficiency of the model, telling us how much room for improvement remains. Recent work has shown that the Bayes error, or equivalently the optimal accuracy, can be estimated from soft labels in binary classification. However, accuracy is often a poor summary of performance in settings with severe class imbalance or noisy annotations, where metrics such as the balanced error rate (BER) and the area under the ROC curve (AUC) are more appropriate. We address this gap with two complementary contributions. (i) Estimation. We propose soft-label-based estimators for the optimal BER and AUC. We first consider the clean setting in which true soft labels and the class prior are known, and then extend the estimators to a more realistic setting in which the class prior is unknown and the observed soft labels are corrupted by an unknown order-preserving transformation, possibly followed by additive noise. In the latter setting, we approximately recover the clean soft labels via isotonic regression with auxiliary hard labels, estimate the class prior with a clipped mean of the hard labels, and derive finite-sample error bounds for the resulting plug-in estimators. (ii) Evaluation. Since the optimum is unobservable on real datasets, evaluating any such estimator is itself nontrivial. We extend the FeeBee framework, originally proposed for evaluating Bayes-error estimators, to the optimal BER and AUC. The resulting procedure provides practical evaluation scores without requiring knowledge of the optimum, and applies to any estimator of the optimal BER or AUC, not only our proposed ones. Experiments on synthetic and real-world datasets validate both the estimators and the evaluation procedure.

1 Introduction

The paper targets Bayes-optimal BER and AUC because ordinary error rate is inadequate under class imbalance or label noise. It proposes soft-label estimators and extends FeeBee to evaluate such estimators without knowing the true optima.

  • Motivation: Bayes-optimal performance is the best value achievable on a task and separates irreducible error from current-model deficiency.A small gap between current and optimal performance indicates limited room for improvement.
  • Prior work: Existing soft-label approaches estimate Bayes error without requiring input features, supporting privacy-sensitive applications.Soft labels encode class membership as probabilities rather than binary labels.
  • Motivation: Error rate can be misleading under severe class imbalance, whereas BER averages per-class errors and AUC summarizes ranking across thresholds.Both BER and AUC are also used under label noise because their optimizers remain unchanged under noisy labels.
  • Contributions: The paper proposes soft-label-based estimators for optimal BER and AUC, first with clean labels and known class prior, then under order-preserving corruption and unknown prior.The optimal BER and AUC depend on the class prior, which is handled explicitly.
  • Contributions: Evaluating optimal BER and AUC estimators on real datasets is difficult because the true optima are unobservable.The paper extends FeeBee by deriving noise-based relationships and scores for this evaluation setting.
  • Contributions: The proposed evaluation procedure applies to any optimal BER or AUC estimator and does not require knowledge of the true optima.This makes the framework usable beyond the estimators introduced in the paper.

2 Estimation from clean soft labels

With clean soft labels, the paper expresses optimal BER and AUC as expectations that yield two unbiased estimators each, then develops variance-based selection criteria, efficient computation, clipping, and finite-sample bounds.

  • Optimal-form estimators: Optimal BER and AUC can each be expressed as expectations of functions of the class posterior, producing two natural unbiased estimators.The alternatives correspond to min and max formulas.
  • Estimator selection: The min-versus-max choice is guided by discriminants whose signs indicate which estimator has smaller variance.The BER and AUC discriminants are estimated from soft labels and selected by their estimated signs.
  • Efficient computation: O(n log n) algorithms compute the proposed AUC estimators and discriminant exactly instead of using Θ(n^2) pairwise summation or approximation.The efficient procedures exploit special structure in the degree-two U-statistics.
  • Clipping: Clipping keeps AUC estimates within the valid range [0.5, 1] and makes each clipped estimator at least as accurate as its unclipped counterpart.The raw estimator can leave the valid range in rare events.
  • Error bounds: The proposed estimators have finite-sample estimation-error bounds, including bounds designed to improve AUC dependence on severe class imbalance.The AUC analysis uses a Bernstein-type inequality for U-statistics rather than bounds whose factor scales as 1/[θ(1−θ)].
  • Unknown class prior: When the class prior is unknown, a clipped sample mean estimates it before forming plug-in BER and AUC estimators.Clipping avoids numerical instability or division by zero from factors involving θ and 1−θ.

3 Estimation from corrupted soft labels

For corrupted soft labels, the paper uses isotonic regression with auxiliary hard labels to recover clean-label estimates, estimates the class prior, and derives plug-in error bounds under noiseless and additive-noise corruption.

  • Corruption model: The corrupted-label setting provides one hard label and a soft label transformed by an unknown increasing function instead of the clean posterior.This models settings such as low-resolution images paired with labels from the original data.
  • Recovery of soft labels: Isotonic regression fits a non-decreasing mapping from corrupted soft labels to hard labels, using fitted values as estimates of the clean soft labels.The pool adjacent violator algorithm computes the monotonic least-squares fit after sorting the corrupted labels.
  • Recovery of soft labels: The recovery algorithm runs in O(n log n) time because sorting dominates the O(n) pool adjacent violator step.Each fitted value is expected to approximate the corresponding true clean soft label.
  • Plug-in estimation: The estimated clean soft labels and a clipped class-prior estimate are plugged into the optimal BER and AUC formulas to obtain finite-sample guarantees.The class-prior estimator converges to θ at rate 1/√n under the stated assumption.
  • Noisy corruption: With additive noise, the corrupted labels follow ξi = f(ηi) + εi under a differentiable order-preserving transformation and zero-mean noise.The noisy model extends the finite-sample results to labels that may not preserve the clean-label ordering.
  • Noisy corruption: Averaging m corrupted hard labels yields estimation errors of order m^-1/2 + n^-1/3, with the additional term decreasing as m increases.The noise standard deviation is at most σ = 1/(2√m) in this example.

4 Real-world evaluation of optimal performance estimators

The paper extends FeeBee to evaluate optimal BER and AUC estimators when the true optima are unobservable on real-world datasets. It injects controlled label noise, derives bounds from the noise transformation, and aggregates violations into estimator scores.

  • The real-world evaluation problem arises because BER* and AUC* are unobservable for real-world data distributions.
  • Controlled label noise replaces each label with an independent random label with probability ν, producing posterior transformation λν(t) = (1 −ν)t + νβ.
  • Theorem 4.1 characterizes the optimal BER and AUC of the noise-injected distribution through their original optimal values.
  • Estimates outside the bounds [LBER(νi), UBER(νi)] are penalized by their violation, and lower aggregated scores indicate better estimators.
  • The evaluation procedure generates N noise-injected datasets at different noise levels and evaluates the estimator on each dataset.
  • Averaging scores over many β values aligns best with variance estimates, while the score can also detect bias exceeding the bound interval width.
  • The same bound-based procedure applies to AUC, with the class prior θ estimated from hard-label sample means when available.

5 Experiments

Experiments on synthetic and real-world soft-label datasets support the proposed BER and AUC estimators, the discriminant-based estimator choice, and the evaluation procedure. Isotonic calibration corrects corrupted soft labels, while averaged evaluation scores align more consistently with variance estimates.

  • Synthetic data: With n = 10,000 Gaussian-mixture samples and class prior θ = 0.2, experiments compare clean, under-confident, and over-confident soft-label settings.The class prior is estimated as unknown, and ground-truth optimal BER and AUC values are computed in closed form.
  • Synthetic data: Proposed BER and AUC estimators cluster near ground-truth values, whereas naive corrupted-label baselines deviate by an order of magnitude more than the confidence-interval width.The results identify isotonic calibration as essential for correcting soft-label corruption.
  • Real-world data: Across real-world datasets, the empirical discriminant generally predicts which min/max BER estimator has lower bootstrap variance.Fashion-MNIST is the sole sign mismatch, and its empirical discriminant is close to zero.
  • Real-world data: For BER and AUC, Table 1 reports empirical discriminants, bootstrap standard-error gaps, and evaluation-score gaps between the min and max formula estimators.The table defines ΔSE and ΔScore as max − min gaps in bootstrap standard error and evaluation score, respectively.
  • Real-world data: Evaluation scores averaged over β ∈ {0.1, 0.2, ..., 0.9} are far more consistent with variance estimates than scores using β = 0.5 or the estimated class prior.The comparison uses three β choices and bootstrapped standard-error differences.

6 Conclusion

The paper develops efficient soft-label estimators for Bayes-optimal BER and AUC, analyzes their theoretical properties, and proposes evaluation without access to the true optima.

  • 6 Conclusion: Soft-label estimators are proposed for the optimal BER and AUC, including clean-label settings with known class prior.The optimal BER classifier thresholds the posterior at the class prior, while the optimal AUC scoring function is the posterior or any strictly increasing transformation.
  • 6 Conclusion: Corrupted soft labels are handled through estimators whose theoretical properties are analyzed under the stated corruption assumptions.The variance and concentration analyses include BER and AUC estimators based on bounded U-statistics.
  • 6 Conclusion: An evaluation procedure assesses optimal BER and AUC estimators without knowledge of the true optima.The procedure is based on noise-injected distributions and can be applied beyond the estimators proposed in the paper.
  • 6 Conclusion: The AUC computation can be reduced from naive O(n^2) time to O(n log n) time by sorting soft labels and using prefix sums.The algorithm computes the relevant estimator and variance quantities after sorting the soft labels.

A.4.2 Proofs of the estimation error bounds

For known class prior, the BER and AUC estimators are bounded U-statistics, enabling concentration-based estimation-error bounds; the AUC bound worsens under severe imbalance.

  • A.4.2 Proofs of the estimation error bounds: Known-prior BER and AUC estimators are U-statistics with bounded kernels, so concentration inequalities yield finite-sample error bounds.The BER estimator has degree one and the AUC estimator degree two.
  • A.4.2 Proofs of the estimation error bounds: The AUC kernel ranges from 1 − 1/(8θ(1−θ)) to 1, making its concentration bound depend on the class prior.This range dependence is absent from the corresponding BER case.
  • A.4.2 Proofs of the estimation error bounds: Under severe class imbalance, the basic AUC bound's factor 1/[8θ(1−θ)] grows as O(1/θ) or O(1/(1−θ)).The blow-up occurs as θ approaches 0 or 1.

A.5.2 Clipped estimator of the class prior and plug-in estimators

The plug-in estimators estimate the unknown class prior with a clipped hard-label mean and combine it with recovered soft labels, yielding finite-sample bounds and asymptotic unbiasedness.

  • A.5.2 Clipped estimator of the class prior and plug-in estimators: Using Hoeffding's inequality to estimate the class prior gives a BER estimation-error bound of order O_p(1/[θ(1−θ)√n]).This dependence is subsequently improved using Bernstein's inequality.
  • A.5.2 Clipped estimator of the class prior and plug-in estimators: The plug-in BER estimator is asymptotically unbiased when the clipped class-prior estimator is used.The associated bound contains a constant independent of θ or n.
  • A.5.2 Clipped estimator of the class prior and plug-in estimators: The plug-in AUC estimator is likewise asymptotically unbiased under the same framework.The conclusion follows from a bound with a constant independent of θ or n.

B Supplementary for Section 3

The supplementary results establish finite-sample guarantees for isotonic-regression recovery and plug-in estimation, and give exact noise-transformation formulas for optimal BER and AUC.

  • B Supplementary for Section 3: Isotonic regression estimates the unknown mean vector under non-decreasing structure, with high-probability error bounds.When the corruption function is increasing, the transformed soft labels preserve the ordering needed for isotonic regression.
  • B Supplementary for Section 3: Theorem 3.1 states high-probability bounds for the BER and AUC plug-in estimators under the corruption model.The proof combines class-prior estimation, soft-label recovery, and concentration bounds.
  • B Supplementary for Section 3: For any noise level ν, the optimal BER and AUC of the noise-injected distribution admit exact expressions in terms of the clean quantities and the corruption map.The derivations use the order-preserving transformation and the class-prior transformation induced by noise.

C.2 Bias sensitivity

The evaluation score detects estimator bias that bootstrap variance misses, with penalties emerging when bias exceeds the admissible interval width. Persistent additive bias is therefore detectable at sufficiently high noise, though rapidly shrinking bias may evade detection.

  • The evaluation score reflects certain estimator biases, unlike bootstrap variance, which measures variance only.
  • Bias larger than UBER(ν) − LBER(ν) produces a positive expected penalty for BER, with the same argument applying to AUC.For AUC, the corresponding interval-width expression replaces uBER with 1 − lAUC.
  • The interval width scales as 1 − ν and approaches zero as ν → 1, strengthening sensitivity at larger noise levels.
  • Any fixed nonzero additive bias persisting across noise levels is expected to be detected at sufficiently large noise levels.A bias shrinking sufficiently fast as ν → 1 may remain undetected.
  • In synthetic experiments, the score averaged over β increased from 0 to 0.029953 for BER and from 0 to 0.040368 for AUC as injected bias increased.Estimator standard deviations remained constant at 0.001241 for BER and 0.001370 for AUC.

D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix

This section derives closed-form optimal BER and AUC expressions for shared-covariance Gaussian mixtures. The derivation uses the posterior-equivalent likelihood score and evaluates its class-conditional error and ranking behavior.

  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: Figure 3 evaluates BER and AUC scores against injected bias, comparing β = 0.5 with averages over β ∈ {0.1, ..., 0.9}.The plotted curves include theoretical lower bounds evaluated at B = b.
  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: Under shared-covariance Gaussian mixtures, Proposition D.1 gives closed-form expressions for the optimal BER and AUC.
  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: The posterior threshold η(x) ≥ θ is equivalent to comparing class-conditional densities, implemented through the score f∗(x) ≥ 0.
  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: The optimal BER follows by evaluating the within-class false-positive and false-negative rates of the score-based classifier.
  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: The score f∗ is a strictly increasing transformation of η(x), so it attains the maximum AUC.
  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: The maximum AUC is obtained from the probability that an independent positive score exceeds an independent negative score.
  • D Closed-form expressions for the optimal BER and AUC under Gaussian mixture models with a shared covariance matrix: When J = 0, the optimal classifier always predicts class 1, yielding BER∗ = 1/2 and AUC∗ = 1/2.

E.1 Estimation on synthetic data

The synthetic experiment evaluates clean and corruption-aware estimators of optimal BER and AUC using analytically known Gaussian-mixture optima. It compares recalibrated and naive corrupted-label approaches with bootstrap confidence intervals.

  • The synthetic experiment uses n = 10,000 samples from a two-component Gaussian mixture with class prior θ = 0.2.
  • The analytically known optima are BER∗ = Φ(−√2) ≈ 0.07865 and AUC∗ = Φ(2) ≈ 0.97725.These values are shown as reference dashed lines in Figure 2.
  • Corruption is generated with inverse beta-calibration maps whose parameter a controls under-confidence or over-confidence, while b = 0.5 preserves symmetry about 0.5.
  • The clean estimator is applied directly to ηi, whereas corrupted settings compare isotonic recalibration against a naive direct application to ξi.
  • The class prior is estimated from soft-label means in the clean setting and hard-label means in corrupted settings, with min-versus-max selection performed on each resample.
  • 95% confidence intervals are computed with the bias-corrected accelerated bootstrap using 1,000 resamples.

E.2.1 Datasets

The real-world evaluation spans computer vision, natural language inference, and academic peer review datasets. These datasets provide soft labels from human judgments or aggregated reviewer information alongside binary or hard labels.

  • The real-world datasets cover computer vision, natural language processing, and academic peer review.
  • CIFAR-10 is converted to animal versus non-animal classes using soft labels from CIFAR-10H.
  • Fashion-MNIST is similarly converted into positive and negative clothing categories using Fashion-MNIST-H soft labels.
  • ChaosNLI supplies 100 hard labels per data point, whose average is used to construct soft labels across SNLI, MNLI, and AbductiveNLI.
  • The ICLR 2017–2025 review dataset contains n = 32,829 instances pairing reviewer-derived soft labels with hard labels.Soft labels are formed from confidence-weighted reviewer scores normalized to [0, 1].

E.2.2 Experiment setup

The experiment evaluates BER* and AUC* estimators under progressively larger violations of order preservation, using synthetic datasets, bootstrap uncertainty, and FeeBee-based scores. It varies corruption noise and measures estimation accuracy against ground-truth optima.

  • Experiment setup: The study evaluates three quantities for each metric and dataset: the min formula, the max formula, and bootstrap uncertainty estimates.Bootstrap confidence intervals use 1,000 resamples and the BCa method.
  • Experiment setup: FeeBee scores use 100 noise levels, theoretical bounds, and three choices of the noise mean β.The choices are β = 0.5, β = θ, and a third choice described in the experimental protocol.
  • Experiment setup: The approximate-monotonicity experiment starts from an under-confident inverse-beta-calibration map and adds Gaussian noise on the logit scale.The corruption is nearly monotone but not exactly monotone, with σ controlling the departure from monotonicity.
  • Experiment setup: Across σ ∈ {0, 0.05, 0.1, 0.2, 0.4, 0.8, 1.6}, the study computes BER* and AUC* estimates, Kendall correlation, and q over 30 independently sampled datasets.Here q = (1 − τ)/2 represents the fraction of reversed pairs.
  • Results: At q ≤ 2.44%, estimates remain close to ground truth with 95% confidence intervals containing the population values; at q ≥ 4.85%, deviations become substantially larger.Estimation error increases progressively as the order-reversal rate grows.
Loading 2609.02304v1…