Undersampling is a Minimax Optimal Robustness Intervention in Nonparametric Classification. (arXiv:2205.13094v1 [cs.LG])

While a broad range of techniques have been proposed to tackle distribution
shift, the simple baseline of training on an $\textit{undersampled}$ 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 …

arxiv classification minimax robustness