Structured Proper Loss Geometries for Multiclass Classification: Theory and Controlled Empirical Evaluation

Technical Summary: Structured Proper Loss Geometries for Multiclass Classification

Problem Statement
Strictly proper scoring rules guarantee that the true conditional class distribution minimizes the expected loss at the population level. However, the curvature of these scores influences optimization dynamics, finite-sample behavior, calibration, and robustness to corrupted labels or class-prior shifts. While cross-entropy (logarithmic score) is the standard baseline, it can lead to miscalibration and overfitting to noisy labels. Existing literature has proposed various objectives for specific failure modes (e.g., focal loss for imbalance, generalized cross-entropy for noise), but there is a need to rigorously analyze how structured modifications to proper scoring rules—specifically through curvature and margin shaping—affect performance without claiming broad superiority over specialized methods.

Methodology
The paper investigates three multiclass objectives, treating them as specific constructions within the framework of Bregman divergences and composite losses:

1. Class-Aware Proper Mahalanobis Loss (CAPM): A structured quadratic Bregman score defined by a generator $F_C(p) = \frac{1}{2}(p-u)^\top A (p-u)$. The matrix $A$ incorporates class-aware structures, including a graph Laplacian ($L_G$) derived from class-centroid similarities and a diagonal term ($D_{tail}$) based on class counts.
2. Hyperbolic Proper Generator Loss (HPG): A strictly proper loss using a generator $F_H(p)$ that combines a quadratic term with constrained log-cosh ridge terms. This introduces bounded curvature and smoothness while maintaining strict propriety.
3. Annealed Probability-Margin Shaping (APMS): An augmentation of HPG that adds a bounded margin penalty $r(p, y)$ with a coefficient $\beta_t$ that anneals toward zero during training. This allows for temporary margin shaping while aiming to converge to the proper HPG objective.

Theoretical Contributions
The authors provide rigorous mathematical analysis establishing the properties of these losses:

• Bounds for CAPM and HPG: Derivation of conditional-regret, curvature, range, and logit-gradient bounds. It is proven that both are strictly proper, with excess conditional risk controlled by the squared Euclidean distance between the predicted and true probability vectors.
• APMS Analysis: Proof of the exact range of the margin penalty on the probability simplex. The authors establish both square-root and linear bounds on the displacement of the conditional minimizer from the true probability vector as a function of the margin coefficient $\beta$. This confirms that while the objective is not strictly proper for $\beta > 0$, the minimizer converges to the true distribution as $\beta \to 0$.
• Gradient Bounds: Derivation of bounds on the loss gradient with respect to logits, showing that the curvature of the generator controls the magnitude of gradients.

Experimental Design
The study employs a controlled, descriptive empirical evaluation using five random seeds across several regimes:

• Datasets: Real-world datasets (Digits, Wisconsin Breast Cancer) and synthetic problems (confusion matrix, long-tail distribution).
• Conditions: Clean labels, symmetric label noise (20%, 40%), pair-flip noise (40%), class imbalance (30:1 ratio), and input corruptions (Gaussian noise, salt-and-pepper, FGSM, PGD).
• Baselines: Cross-entropy (CE) serves as the primary reference. Comparisons are made against established noisy-label methods (e.g., Generalized Cross-Entropy, Symmetric Cross-Entropy, Active-Passive Loss) and long-tail methods (e.g., Balanced Softmax, Logit Adjustment).
• Metrics: Accuracy, Balanced Accuracy, Negative Log-Likelihood (NLL), Brier Score, and Expected Calibration Error (ECE).
• Statistical Rigor: The study explicitly avoids claiming statistical significance due to the limited number of seeds (five), noting that the smallest attainable Wilcoxon p-value is 0.0625. Results are interpreted descriptively based on effect patterns.

Key Results

• Clean Data: CAPM, HPG, and APMS perform comparably to cross-entropy on clean data across all datasets.
• Noisy Labels: On the Digits dataset with 40% symmetric label noise, the proposed structured losses show modest improvements over cross-entropy but are outperformed by specialized noisy-label baselines (SCE, GCE, APL, MAE) in terms of accuracy, NLL, and Brier score.
• Long-Tail Learning: In the synthetic 30:1 long-tail experiment, the proposed methods fail to address the prior shift effectively, achieving balanced accuracy near 0.16 (similar to cross-entropy). In contrast, explicit prior-adjustment methods (Balanced Softmax, Logit Adjustment) achieve balanced accuracy above 0.62.
• Ablations: Removing the specific structural components (graph terms in CAPM, ridge terms in HPG, or margin coefficients in APMS) does not consistently degrade performance, suggesting these specific additions did not provide a clear benefit in the evaluated settings.
• Calibration and Robustness: Post-hoc temperature scaling improves calibration for all methods. Input corruption and adversarial attacks show only small descriptive differences among models trained on clean data.

Significance and Claims
The paper modestly claims that its formulations are mathematically valid and empirically testable examples of how proper-score curvature and margin shaping can be constructed.

• Theoretical Validity: The proofs successfully establish that the proposed losses are strictly proper (or converge to properness) and satisfy specific curvature and gradient bounds.
• Empirical Limitations: The experiments do not support a claim of general superiority. The structured objectives do not consistently outperform specialized methods for noisy labels or long-tailed learning.
• Primary Contribution: The work serves as a controlled study to distinguish between population identification (guaranteed by properness) and finite-sample robustness (which depends on specific loss geometry and is not automatically improved by curvature modifications alone). The authors conclude that while the formulations are sound, their utility in replacing established losses requires further validation on larger datasets, stronger architectures, and realistic noise models.