Training Over-parameterized Models with Non-decomposable Objectives

Harikrishna Narasimhan, Aditya Krishna Menon

Abstract

Many modern machine learning applications come with complex and nuanced design goals such as minimizing the worst-case error, satisfying a given precision or recall target, or enforcing group-fairness constraints. Popular techniques for optimizing such non-decomposable objectives reduce the problem into a sequence of cost-sensitive learning tasks, each of which is then solved by re-weighting the training loss with example-specific costs. We point out that the standard approach of re-weighting the loss to incorporate label costs can produce unsatisfactory results when used to train over-parameterized models. As a remedy, we propose new cost-sensitive losses that extend the classical idea of logit adjustment to handle more general cost matrices. Our losses are calibrated, and can be further improved with distilled labels from a teacher model. Through experiments on benchmark image datasets, we showcase the effectiveness of our approach in training ResNet models with common robust and constrained optimization objectives.

1. Introduction: The Failure of Loss Re-weighting

In real-world machine learning, objectives often extend beyond simple accuracy to non-decomposable metrics like fairness, precision/recall targets, or robustness (minimizing worst-case error). The standard approach to these problems is cost-sensitive learning (CSL), where different types of errors are assigned specific weights.

However, modern neural networks are typically over-parameterized, possessing enough capacity to achieve near-zero training error by memorizing labels. In this regime, multiplying a zero loss by a weight has no effect. The model separates the training data perfectly but fails to learn the margins necessary for optimal performance on complex metrics during inference. This "memorization pitfall" renders traditional re-weighting ineffective, as the model finds a way to make the loss zero for every sample regardless of the weight.

Figure 1: Comparison of Unweighted, Re-weighted, and Logit-adjusted methods. Re-weighting fails to improve accuracy on the targeted class in over-parameterized models, whereas logit adjustment succeeds.

2. Methodology: Logit-Adjusted and Hybrid Losses

To address the limitations of re-weighting, we propose shifting decision boundaries in the logit space rather than scaling the outer loss. This acts as a "soft margin," forcing the model to get predictions right by a specific margin of confidence.

2.1 Logit-Adjusted Loss ($L^{LA}$)

Instead of scaling the cross-entropy loss, we subtract a cost-dependent term from the logits inside the softmax function. This forces the model to maintain a larger margin for high-priority classes, even when training error is low.

2.2 Hybrid and Distillation Losses

For complex scenarios with non-diagonal gain matrices (e.g., coverage constraints), we introduce hybrid losses ($L^{hyb}$ and $L^{SMS}$) that combine logit shifts with nuanced outer weighting. Furthermore, we extend this to knowledge distillation ($L^{dis}$), using a hyper-parameter $\gamma$ to balance teacher labels between outer weights and internal logit adjustments. Crucially, these losses are theoretically calibrated, ensuring they yield optimal classifiers in the large-sample limit.

3. Experiments and Results

We evaluated our approach on long-tailed (imbalanced) versions of CIFAR-10, CIFAR-100, and TinyImageNet, with imbalance ratios up to 100:1.

3.1 Maximizing Worst-Case Recall

The primary task was to maximize the minimum recall across all classes. As shown in the results below, logit adjustment significantly outperforms both Empirical Risk Minimization (ERM) and standard re-weighting.

Extracted table from page 7 of Training Over-parameterized Models with Non-decomposable Objectives

On CIFAR-10-LT, the logit-adjusted approach achieved a minimum recall of 0.721, compared to 0.592 for re-weighting. Similar gains were observed in CIFAR-100-LT and TinyImageNet-LT.

3.2 Coverage Constraints and Distillation

In tasks requiring specific prediction frequencies (coverage), our hybrid losses met targets while maintaining high average recall. Additionally, the distillation variant nearly doubled the minimum recall on CIFAR-100-LT compared to standard teacher-student setups, reaching 0.467.

4. Conclusion

Logit adjustment provides a robust, theoretically grounded alternative to loss re-weighting for training high-capacity models with complex objectives. While the approach relies on large-sample assumptions and requires hyper-parameter tuning, it effectively bypasses the memorization pitfall. Future work includes extending these principles to object detection and sequence modeling.

Summary updated

Abstract

Many modern machine learning applications come with complex and nuanced design goals such as minimizing the worst-case error, satisfying a given precision or recall target, or enforcing group-fairness constraints. Popular techniques for optimizing such non-decomposable objectives reduce the problem into a sequence of cost-sensitive learning tasks, each of which is then solved by re-weighting the training loss with example-specific costs. We point out that the standard approach of re-weighting the loss to incorporate label costs can produce unsatisfactory results when used to train over-parameterized models. As a remedy, we propose new cost-sensitive losses that extend the classical idea of logit adjustment to handle more general cost matrices. Our losses are calibrated, and can be further improved with distilled labels from a teacher model. Through experiments on benchmark image datasets, we showcase the effectiveness of our approach in training ResNet models with common robust and constrained optimization objectives.
BibTeX
@inproceedings{narasimhan2021training,
  author = {Harikrishna Narasimhan and Aditya Krishna Menon},
  title = {{Training Over-parameterized Models with Non-decomposable Objectives}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Y0fS_1N0rsk},
}
Figure