Minimax Generalized Cross-Entropy
| Authors | Kartheek Bondugula et al. |
| Year | 2026 |
| Field | Statistics / ML |
| arXiv | 2603.19874 |
| Download | |
| Categories | stat.ML, cs.LG |
Abstract
Loss functions play a central role in supervised classification. Cross-entropy (CE) is widely used, whereas the mean absolute error (MAE) loss can offer robustness but is difficult to optimize. Interpolating between the CE and MAE losses, generalized cross-entropy (GCE) has recently been introduced to provide a trade-off between optimization difficulty and robustness. Existing formulations of GCE result in a non-convex optimization over classification margins that is prone to underfitting, leading to poor performances with complex datasets. In this paper, we propose a minimax formulation of generalized cross-entropy (MGCE) that results in a convex optimization over classification margins. Moreover, we show that MGCEs can provide an upper bound on the classification error. The proposed bilevel convex optimization can be efficiently implemented using stochastic gradient computed via implicit differentiation. Using benchmark datasets, we show that MGCE achieves strong accuracy, faster convergence, and better calibration, especially in the presence of label noise.
Engineering Breakdown
Plain English
This paper addresses a fundamental problem in classification: choosing the right loss function that balances optimization ease with robustness to noisy labels. The authors propose Minimax Generalized Cross-Entropy (MGCE), which reformulates the existing Generalized Cross-Entropy (GCE) loss as a convex optimization problem over classification margins, whereas prior GCE formulations were non-convex and prone to underfitting. The key finding is that MGCE achieves better performance on complex datasets while providing theoretical guarantees—specifically, an upper bound on classification error. This solves a practical bottleneck where engineers had to choose between standard cross-entropy (easy to optimize but not robust) or MAE-based losses (robust but numerically difficult).
Core Technical Contribution
The core innovation is a minimax reformulation that converts GCE from a non-convex margin-based optimization into a convex problem. Instead of directly interpolating between CE and MAE in the standard way, the authors frame the problem as a two-player game: one player minimizes over model parameters while another maximizes over a margin variable, which guarantees convexity in the margin space. This reformulation is elegant because it preserves the robustness properties of MAE-based losses while recovering the optimization tractability of cross-entropy. Additionally, they provide a theoretical result showing MGCE produces an upper bound on 0-1 classification error, giving practitioners a principled way to reason about model quality.
How It Works
The mechanism starts with the standard supervised learning setup: given input features and class labels, you want to learn a classifier. Traditional GCE loss interpolates between cross-entropy and MAE using a hyperparameter that trades off optimization difficulty versus robustness. The problem is this creates a non-convex optimization landscape over the classification margin (the distance of each example from the decision boundary). MGCE reformulates this as a minimax problem: for each training example, you have an inner maximization over a margin threshold (how confident the model must be) and an outer minimization over model weights. The inner maximization creates convexity guarantees because it's optimizing over a scalar margin per sample. During training, you alternate between updating model parameters (with stochastic gradient descent) and updating the margin variables (which have closed-form updates). The loss function itself is a weighted combination that dynamically penalizes misclassified examples more heavily when they are close to the decision boundary, which encourages the model to learn more discriminative features.
Production Impact
In production classification systems, this directly improves robustness to label noise and annotation errors, which is critical for real-world datasets where perfect labeling is rare and expensive. Engineers currently training large classifiers with standard cross-entropy could swap in MGCE with minimal code changes—it's a drop-in loss function replacement—but gain better performance on noisy datasets without sacrificing training speed. The convex formulation over margins means more stable gradient updates and fewer convergence issues, reducing debugging time and hyperparameter tuning. However, there are trade-offs: MGCE requires tracking an additional margin variable per sample (modest memory overhead), the hyperparameter controlling CE-to-MAE interpolation still needs tuning, and the method is most beneficial when label noise is significant; for clean, well-curated datasets, the improvement over standard CE may be marginal. The theoretical upper bound on classification error also provides a principled stopping criterion and early stopping signal, which can reduce unnecessary training and deployment costs.
Limitations and When Not to Use This
The paper's title appears truncated ('The proposed bile'), so the full scope of contributions may not be completely clear from the abstract alone. The approach assumes that label noise and robustness are the primary pain points; it doesn't directly address other common failure modes like class imbalance, distribution shift, or adversarial robustness, though it may help indirectly. The convex formulation applies specifically to the margin-based optimization, but convergence speed and practical wall-clock time comparisons with standard GCE are not detailed in the abstract, so it's unclear if practitioners see real speedups in practice. The method still requires careful tuning of the interpolation hyperparameter, meaning it doesn't eliminate the hyperparameter search problem entirely—it just shifts it. Finally, the theoretical upper bound on classification error is only as useful as the margin variables themselves; if the optimization gets stuck in a local minimum of the margin space, the bound may be loose.
Research Context
This work builds on the family of generalized cross-entropy losses introduced in recent years (roughly 2019-2024) that sought to bridge robust loss functions like Mean Absolute Error with the optimization-friendly properties of cross-entropy. The lineage goes: standard cross-entropy → symmetric cross-entropy and focal loss for handling class imbalance → generalized cross-entropy as a principled interpolation. MGCE represents a maturation of this research direction by introducing convex geometry and game-theoretic structure, which is a common pattern in modern loss function design. The upper bound result connects to margin theory in statistical learning, specifically the relationship between margins and generalization—showing that MGCE is not just an ad-hoc interpolation but a principled approach grounded in VC-dimension-style learning theory. This opens research directions toward adaptive margin schemes, extensions to multi-class and multi-label settings with margins, and potential applications in semi-supervised learning where margin regularization has proven effective.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::