Training Over-parameterized Models with Non-decomposable Objectives

Harikrishna Narasimhan, Aditya Krishna Menon

Introduction

Standard loss re-weighting often fails to optimize complex metrics—such as worst-case recall or fairness—in deep learning. Because over-parameterized models have the capacity to simply memorize the training data, traditional class weights become ineffective during optimization. This paper introduces new "logit-adjusted" losses that shift decision boundaries during training, providing a robust and theoretically grounded way to optimize non-decomposable objectives in modern neural networks.

The Challenge of Non-Decomposable Objectives

In traditional machine learning, we usually minimize misclassification error. This is a "decomposable" objective because it is simply the sum of losses over individual samples. However, real-world applications frequently require "non-decomposable" goals, such as maximizing the recall of the rarest class (worst-case recall) or ensuring strict group-fairness constraints.

The standard "reduction" approach turns these complex goals into a series of cost-sensitive learning tasks, where different classes are assigned different weights. While this works for simpler models, it breaks down for over-parameterized models like deep neural networks. Because these models can achieve near-zero training error (memorization), the applied weights become irrelevant: a large weight multiplied by a near-zero loss is still zero. Consequently, the model fails to learn the necessary trade-offs to satisfy the complex objective on new, unseen data.

Proposed Methods: Shifting Instead of Scaling

To overcome the memorization trap, the authors propose moving away from scaling the loss (re-weighting) and instead focus on shifting the inputs to the loss function.

  1. Logit Adjustment ($\ell^{LA}$): For simple class-specific weights (diagonal gain matrices), the authors introduce a log-offset to the logits. This forces the model to maintain a "margin" between classes proportional to their importance. Crucially, this margin persists even as the training error approaches zero.
  2. Hybrid Loss ($\ell^{hyb}$): For more complex scenarios where the cost of confusing class A for class B differs from confusing it for class C (non-diagonal gain matrices), they propose a hybrid approach. This combines logit adjustment (to handle class-specific importance) with an outer weighting (to handle specific pairwise costs).
  3. Calibration: The authors prove that these new losses are "Fisher consistent." In the limit of infinite data, minimizing these surrogate losses is mathematically guaranteed to yield the optimal classifier for the original non-decomposable objective.
  4. Teacher Distillation: These losses can also be integrated with knowledge distillation, using soft labels from a teacher model to further regularize the network and prevent the memorization trap.

Key Insights: Escaping the Memorization Trap

Comparison of Unweighted, Re-weighted, and Logit-adjusted methods as class weighting increases.
  • Active vs. Passive Strategies: The core insight is that standard re-weighting is a "passive" strategy. If a model is powerful enough to fit every training point perfectly, it never "feels" the weights. Logit adjustment, on the other hand, is an "active" strategy that fundamentally changes the geometry of the decision boundary.
  • Shifting vs. Scaling: Scaling a loss changes how much we care about an error after it happens. Shifting a logit changes the requirement for what counts as a correct prediction, forcing the model to be more "confident" on high-priority classes.
  • The Two-Dataset Strategy: To optimize the gain matrix (the weights/offsets), the authors use a validation set to update the Lagrange multipliers while using the training set to update the model parameters. This prevents the model from simply "gaming" the weights on the training data.

Experimental Results

The researchers evaluated their approach on "long-tailed" (imbalanced) versions of standard image benchmarks: CIFAR-10-LT, CIFAR-100-LT, and TinyImageNet-LT. These datasets are ideal for testing non-decomposable objectives because standard models typically fail on the rare "tail" classes.

Performance comparison on long-tailed datasets showing Average and Minimum Recall.

The proposed logit-adjusted losses significantly outperformed standard re-weighting across multiple tasks:

  • Worst-case Recall: On CIFAR-10-LT, the logit-adjusted approach achieved a minimum recall of 0.731, compared to just 0.619 for standard re-weighting.
  • Coverage Constraints: When tasked with ensuring the model predicts a class at least 95% as often as its actual prevalence, the hybrid losses successfully met the constraints while maintaining higher average recall than the baselines.
  • Comparison to Post-hoc Shifting: The method even outperformed post-hoc strategies (adjusting a pre-trained model's thresholds), suggesting that incorporating these costs during training leads to better underlying feature representations.
  • Distillation Boost: Using soft labels from a teacher model improved all methods, but the logit-adjusted student still maintained a competitive edge.

Limitations and Future Directions

  • Large Sample Assumption: The calibration proofs hold in the "large sample limit." More work is needed to understand how these losses behave in extremely low-data regimes.
  • Margin Theory: While the losses act like margins, a formal theoretical link between logit adjustment and generalization margins in over-parameterized settings remains an open area for research.
  • Broader Fairness Applications: While the paper touches on fairness, the experiments are limited to image classification. Applying these techniques to high-stakes tabular data (e.g., lending or hiring) would be a vital next step to ensure no unforeseen biases are introduced in real-world deployments.

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