# Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 20 of 20)

- [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)
- [Long-tail learning via logit adjustment](https://mlsanity.com/paper/2007.07314/) (2020)
- [Just Train Twice: Improving Group Robustness without Training Group Information](https://mlsanity.com/paper/2107.09044/) (2021)
- [Detecting and Correcting for Label Shift with Black Box Predictors](https://mlsanity.com/paper/1802.03916/) (2018)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [What is the Effect of Importance Weighting in Deep Learning?](https://mlsanity.com/paper/1812.03372/) (2018)
- [Rethinking the Value of Labels for Improving Class-Imbalanced Learning](https://mlsanity.com/paper/2006.07529/) (2020)
- [Demographic Dialectal Variation in Social Media: A Case Study of African-American English](https://mlsanity.com/paper/1608.08868/) (2016)
- [Simple data balancing achieves competitive worst-group-accuracy](https://mlsanity.com/paper/2110.14503/) (2021)
- [Strike (with) a Pose: Neural Networks Are Easily Fooled by Strange Poses of Familiar Objects](https://mlsanity.com/paper/1811.11553/) (2018)
- [Tilted Empirical Risk Minimization](https://mlsanity.com/paper/2007.01162/) (2020)
- [Identifying and Compensating for Feature Deviation in Imbalanced Deep Learning](https://mlsanity.com/paper/2001.01385/) (2020)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [On the Value of Target Data in Transfer Learning](https://mlsanity.com/paper/2002.04747/) (2020)
- [Understanding the role of importance weighting for deep learning](https://mlsanity.com/paper/2103.15209/) (2021)
- [Minimax optimal approaches to the label shift problem in non-parametric settings](https://mlsanity.com/paper/2003.10443/) (2020)
- [Is Importance Weighting Incompatible with Interpolating Classifiers?](https://mlsanity.com/paper/2112.12986/) (2021)
- [Minimax Lower Bounds for Cost Sensitive Classification](https://mlsanity.com/paper/1805.07723/) (2018)

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

- [When More is Less: Incorporating Additional Datasets Can Hurt Performance By Introducing Spurious Correlations](https://mlsanity.com/paper/2308.04431/) (2023)
- [Malign Overfitting: Interpolation Can Provably Preclude Invariance](https://mlsanity.com/paper/2211.15724/) (2022)
- [The Group Robustness is in the Details: Revisiting Finetuning under Spurious Correlations](https://mlsanity.com/paper/2407.13957/) (2024)

## Abstract (arXiv)

While a broad range of techniques have been proposed to tackle distribution shift, the simple baseline of training on an textitundersampled balanced dataset often achieves close to state-of-the-art-accuracy across several popular benchmarks. This is rather surprising, since undersampling algorithms discard excess majority group data. To understand this phenomenon, we ask if learning is fundamentally constrained by a lack of minority group samples. We prove that this is indeed the case in the setting of nonparametric binary classification. Our results show that in the worst case, an algorithm cannot outperform undersampling unless there is a high degree of overlap between the train and test distributions (which is unlikely to be the case in real-world datasets), or if the algorithm leverages additional structure about the distribution shift. In particular, in the case of label shift we show that there is always an undersampling algorithm that is minimax optimal. In the case of group-covariate shift we show that there is an undersampling algorithm that is minimax optimal when the overlap between the group distributions is small. We also perform an experimental case study on a label shift dataset and find that in line with our theory, the test accuracy of robust neural network classifiers is constrained by the number of minority samples.