Improved Balanced Classification with Theoretically Grounded Loss Functions

AI summary

Overview

Research area: Machine learning — specifically multi-class classification under class imbalance and the statistical learning theory of surrogate loss functions (Bayes-consistency and ℋ-consistency bounds).

Technical level: Advanced (the paper is centered on consistency theory and general cross-entropy loss families; the empirical portion is more accessible).

One-sentence scope: The paper introduces two surrogate loss families for the balanced loss — Generalized Logit-Adjusted (GLA) and Generalized Class-Aware weighted (GCA) — proves consistency guarantees for both, and reports experiments on CIFAR-10, CIFAR-100, and Tiny ImageNet.

What This Paper Is About

In multi-class problems with skewed label distributions, the balanced loss gives every class equal importance regardless of frequency, but it cannot be optimized directly. The paper asks how to design tractable surrogate losses that are provably faithful to the balanced loss, and it proposes two families that generalize existing approaches (Logit-Adjusted losses and class-weighted losses) to the broader general cross-entropy (GCE) family. The goal is to obtain both stronger theory — especially in terms of dependence on the minimum class probability 𝗉_min — and better empirical performance than straightforward class-weighted losses and Logit-Adjusted (LA) losses.

Key Contributions

1. Two new surrogate loss families. Generalized Logit-Adjusted (GLA) losses extend Logit-Adjusted losses (which shift logits based on class priors) to the general cross-entropy loss family, and Generalized Class-Aware weighted (GCA) losses extend standard class-weighted losses by adding class-dependent confidence margins ρ_y and by extending them to the general cross-entropy family.

2. A consistency analysis distinguishing the two families. GLA losses are shown to be Bayes-consistent, but only ℋ-consistent for complete (i.e., unbounded) hypothesis sets, with ℋ-consistency bounds that depend inversely on the minimum class probability 𝗉_min, scaling at least as 1/𝗉_min. GCA losses are shown to be ℋ-consistent for any hypothesis set that is bounded or complete, with bounds scaling more favorably as 1/√𝗉_min.

3. A counterexample for Logit-Adjusted losses. The paper shows that the LA loss with τ = 1 (i.e., GLA with q = 0) is not ℋ-consistent with respect to the balanced loss for certain bounded hypothesis sets, using a two-dimensional construction with x₁ ~ U[0,1], x₂ | x₁ ~ 𝒩(y x₁, x₁²), ℙ(+1) = 1/8, and a hypothesis set of linear models with ‖w_y‖ = 100.

4. Empirical evaluation. Experiments on CIFAR-10, CIFAR-100, and Tiny ImageNet show that both GCA losses with calibrated class-dependent confidence margins and GLA losses can greatly outperform straightforward class-weighted losses as well as LA losses, with GLA generally slightly better on common benchmarks and GCA showing a slight edge in highly imbalanced settings.

Main Findings

• GLA is Bayes-consistent, GCA is more broadly ℋ-consistent. GLA losses are Bayes-consistent for any q ∈ [0, 1), but ℋ-consistency only holds for complete hypothesis sets. GCA losses are ℋ-consistent for any hypothesis set that is bounded or complete.

• Different scaling in 𝗉_min. GLA ℋ-consistency bounds scale as 1/𝗉_min when q = 0 and more generally as (1/𝗉_min)^{1/(1−q)} for q ∈ (0, 1). GCA bounds scale as 1/√𝗉_min, which the paper describes as significantly stronger in imbalanced settings.

• The LA loss is only Bayes-consistent at τ = 1. For τ ≠ 1, the LA loss is not Bayes-consistent with respect to the balanced loss; the paper states that this is why optimal tuning of τ lacks a theoretical guarantee.

• Explicit GLA bound forms. For a complete hypothesis set, the GLA bound uses Γ(t) = √(2t)/𝗉_min when q = 0, and Γ(t) = √(2t) / ((𝗉_min)^{1/(1−q)} (1−q)^{1/2}) for q ∈ (0, 1). When the approximation error 𝒜_{ℓ_GLA}(ℋ) = 0, the bound simplifies to a form without the minimizability gap.

• A general transfer result for GCA. Theorem 5 shows that if a GCE loss ℓ_GCE is ℋ-consistent with respect to ℓ_{0−1} with Γ(t) = β t^α for α ∈ (0, 1] and β > 0, then ℓ_GCA is ℋ-consistent with respect to the balanced loss with Γ̄(t) = β (1/𝗉_min)^{1−α} t^α. Corollary 6 specializes this to common Ψ choices; for Ψ(t) = −log(t), α = 1/2 and β = √2, and for Ψ(t) = (1/q)(1 − t^q) with q ∈ (0, 1), α = 1/2 and β = √(2n^q).

• Class-weighted cross-entropy has a known failure mode. The paper notes prior work (Byrd and Lipton) showing that in separable cases class-weighted cross-entropy may still yield zero-training-loss solutions that do not meaningfully shift decision boundaries.

• Default margin choice. The ρ_k values can be tuned, but the paper follows Cortes et al. (2025) in using values near [m_k^{1/3}]_k, where m_k is the number of samples in class k, and reports that GCA losses are robust to variations around these values.

• Comparable computational cost. For fixed hyperparameters, GLA and GCA losses cost about the same as standard networks trained with cross-entropy loss, and the paper states they work with common optimizers such as SGD, Adam, and AdaGrad.

• Numerical results are not reported in the provided excerpt. The text states that experiments were run on CIFAR-10, CIFAR-100, and Tiny ImageNet and summarizes the relative outcomes, but no accuracy figures, dataset sizes, model architectures, or per-benchmark numbers appear in the content provided.

Methodology in Plain English

The authors work within an established theoretical framework. They start from the balanced loss — which weights each misclassification by the inverse of the true class probability, 1/𝗉(y) — and a lemma (Lemma 1) that expresses that loss's best-in-class conditional error and conditional regret in closed form. They then define their two loss families on top of the general cross-entropy (GCE) family, whose Ψ^q function recovers the logistic loss at q = 0, a generalized cross-entropy loss for q ∈ (0, 1) that is known for robustness to label noise, and the mean absolute error at q = 1.

GLA is built by adding a class-prior bias term log(𝗉(y)) / (1 − q) to the logits, which in the rewritten form acts as a pairwise margin adjustment depending on relative class frequencies. GCA is built by dividing the GCE loss by 𝗉(y) and dividing logits by class-specific confidence margins ρ_y.

For the theory, the authors characterize Bayes classifiers to prove (or disprove) Bayes-consistency, and they prove ℋ-consistency bounds — non-asymptotic inequalities relating the excess balanced-loss error to the excess surrogate error, optionally plus a minimizability gap ℳ_ℓ(ℋ), which is non-negative and bounded above by the approximation error. The GLA proof defines a Gibbs distribution induced by the hypothesis and applies a Pinsker-type inequality; the GCA proof constructs new conditional probabilities q(y|x) together with a normalization factor Z(x) = Σ_y 𝗉(y|x)/𝗉(y) ≤ 1/𝗉_min, which maps the balanced-loss and GCA regrets onto the zero-one and GCE regrets under the new distribution.

Empirically, they compare GLA and GCA against class-weighted losses and LA losses on three image benchmarks, using the 1/3-power-of-class-count heuristic as the default starting point for the margin parameters.

Why This Matters

Impact on research. The paper sharpens the theory of surrogates for the balanced loss by separating two properties that are often conflated: Bayes-consistency (asymptotic, over all measurable functions) and ℋ-consistency (non-asymptotic, for a specific hypothesis class). It also shows that the popular Logit-Adjusted loss is not Bayes-consistent away from τ = 1 and not ℋ-consistent even at τ = 1 for bounded hypothesis sets, which reframes how practitioners should think about tuning that temperature parameter. GCA's 1/√𝗉_min scaling versus GLA's 1/𝗉_min scaling provides a concrete theoretical basis for choosing between the two families.

Real-world applications (the settings the paper itself names as motivation):

• Medical diagnosis, where rare conditions are the classes most likely to be underrepresented.
• Fraud detection, where fraudulent cases are a small fraction of all transactions.
• Rare event prediction, where skew in the label distribution is the defining characteristic.
• Federated learning, where imbalance across clients can bias models toward heavy users.

Industry relevance. The balanced loss is tied to metrics such as balanced accuracy and macro-F1, and the paper links equal-per-class weighting to fairness across demographic groups and to long-tailed datasets. Both loss families cost the same as ordinary cross-entropy training once hyperparameters are fixed, and GCA comes with a suggested default for its margin parameters, which makes adoption in existing deep-learning pipelines low-friction.

Future Directions

• Understanding the gap between theory and practice. The theory favors GCA's 1/√𝗉_min scaling, but the paper reports GLA performing slightly better on common benchmarks and GCA only slightly better in highly imbalanced settings. Reconciling the theory with the observed crossover is left open in the provided content.

• Validating the margin heuristic beyond the studied settings. The choice ρ_k ≈ m_k^{1/3} is justified by a separable-case derivation adapted from Cortes et al. (2025); whether it remains near-optimal at larger scale, with other architectures, or under noisy labels is not established in the excerpt.

• Extending the counterexample's implications. The bounded-hypothesis-set counterexample shows LA is not ℋ-consistent, but the practical consequences for bounded or constrained networks (a common regime) are not quantified.

• Broadening the empirical study. The excerpt reports no numerical results or dataset statistics; the full experimental protocol, class-imbalance ratios, tuning procedures, and comparisons against the wider set of methods discussed in Appendix A are needed to judge the practical claims.

Target Audience

This paper is most valuable to machine learning researchers working on learning theory, surrogate loss design, or class imbalance, and to theoretically minded graduate students who need a rigorous treatment of Bayes-consistency versus ℋ-consistency. Practitioners who train classifiers on long-tailed or highly skewed data — in medical imaging, fraud detection, or federated systems — will find the GLA and GCA loss formulations and the default margin heuristic directly actionable, though the consistency proofs require comfort with statistical learning theory notation. Readers looking primarily for benchmark tables will need the full paper, since the provided content summarizes outcomes qualitatively rather than numerically.

Authors’ abstract

The balanced loss is a widely adopted objective for multi-class classification under class imbalance. By assigning equal importance to all classes, regardless of their frequency, it promotes fairness and ensures that minority classes are not overlooked. However, directly minimizing the balanced classification loss is typically intractable, which makes the design of effective surrogate losses a central question. This paper introduces and studies two advanced surrogate loss families: Generalized Logit-Adjusted (GLA) loss functions and Generalized Class-Aware weighted (GCA) losses. GLA losses generalize Logit-Adjusted losses, which shift logits based on class priors, to the broader general cross-entropy loss family. GCA loss functions extend the standard class-weighted losses, which scale losses inversely by class frequency, by incorporating class-dependent confidence margins and extending them to the general cross-entropy family. We present a comprehensive theoretical analysis of consistency for both loss families. We show that GLA losses are Bayes-consistent, but only $H$-consistent for complete (i.e., unbounded) hypothesis sets. Moreover, their $H$-consistency bounds depend inversely on the minimum class probability, scaling at least as $1/\mathsf p_{\min}$. In contrast, GCA losses are $H$-consistent for any hypothesis set that is bounded or complete, with $H$-consistency bounds that scale more favorably as $1/\sqrt{\mathsf p_{\min}}$, offering significantly stronger theoretical guarantees in imbalanced settings. We report the results of experiments demonstrating that, empirically, both the GCA losses with calibrated class-dependent confidence margins and GLA losses can greatly outperform straightforward class-weighted losses as well as the LA losses. GLA generally performs slightly better in common benchmarks, whereas GCA exhibits a slight edge in highly imbalanced settings.