# Training Over-parameterized Models with Non-decomposable Objectives

arXiv: https://arxiv.org/abs/2107.04641 · HTML: https://mlsanity.com/paper/2107.04641/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 113 references that are in the map.
- First posted on arXiv 9 Jul 2021.

## Builds on (most cited first, 30 of 48)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Decoupling Representation and Classifier for Long-Tailed Recognition](https://mlsanity.com/paper/1910.09217/) (2019)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Long-tail learning via logit adjustment](https://mlsanity.com/paper/2007.07314/) (2020)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Born Again Neural Networks](https://mlsanity.com/paper/1805.04770/) (2018)
- [A systematic study of the class imbalance problem in convolutional neural networks](https://mlsanity.com/paper/1710.05381/) (2017)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [Balanced Meta-Softmax for Long-Tailed Visual Recognition](https://mlsanity.com/paper/2007.10740/) (2020)
- [An Investigation of Why Overparameterization Exacerbates Spurious Correlations](https://mlsanity.com/paper/2005.04345/) (2020)
- [Equalization Loss for Long-Tailed Object Recognition](https://mlsanity.com/paper/2003.05176/) (2020)
- [No Subclass Left Behind: Fine-Grained Robustness in Coarse-Grained Classification Problems](https://mlsanity.com/paper/2011.12945/) (2020)
- [Distribution Alignment: A Unified Framework for Long-tail Visual Recognition](https://mlsanity.com/paper/2103.16370/) (2021)
- [Cost Sensitive Learning of Deep Feature Representations from Imbalanced Data](https://mlsanity.com/paper/1508.03422/) (2015)
- [Seesaw Loss for Long-Tailed Instance Segmentation](https://mlsanity.com/paper/2008.10032/) (2020)
- [Rethinking Class-Balanced Methods for Long-Tailed Visual Recognition from a Domain Adaptation Perspective](https://mlsanity.com/paper/2003.10780/) (2020)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Distribution-Balanced Loss for Multi-Label Classification in Long-Tailed Datasets](https://mlsanity.com/paper/2007.09654/) (2020)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [The Devil is in the Tails: Fine-grained Classification in the Wild](https://mlsanity.com/paper/1709.01450/) (2017)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Satisfying Real-world Goals with Dataset Constraints](https://mlsanity.com/paper/1606.07558/) (2016)

## Built on by (most cited first, 11 of 11)

- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Long-Tailed Partial Label Learning via Dynamic Rebalancing](https://mlsanity.com/paper/2302.05080/) (2023)
- [Robust Distillation for Worst-class Performance](https://mlsanity.com/paper/2206.06479/) (2022)
- [Importance Tempering: Group Robustness for Overparameterized Models](https://mlsanity.com/paper/2209.08745/) (2022)
- [Cost-Sensitive Self-Training for Optimizing Non-Decomposable Metrics](https://mlsanity.com/paper/2304.14738/) (2023)
- [A comprehensive theoretical framework for the optimization of neural networks classification performance with respect to weighted metrics](https://mlsanity.com/paper/2305.13472/) (2023)
- [Selective Mixup Fine-Tuning for Optimizing Non-Decomposable Objectives](https://mlsanity.com/paper/2403.18301/) (2024)
- [DRAGON: Robust Classification for Very Large Collections of Software Repositories](https://mlsanity.com/paper/2602.09071/) (2026)
- [Cost-Sensitive Learning for Long-Tailed Temporal Action Segmentation](https://mlsanity.com/paper/2503.18358/) (2025)
- [FedFACT: A Provable Framework for Controllable Group-Fairness Calibration in Federated Learning](https://mlsanity.com/paper/2506.03777/) (2025)
- [Demystifying the Optimal Fair Classifier in Multi-Class Classification](https://mlsanity.com/paper/2606.00656/) (2026)

## Abstract (arXiv)

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.