  When facing data with imbalanced classes or groups, practitioners follow an
intriguing strategy to achieve best results. They throw away examples until the
classes or groups are balanced in size, and then perform empirical risk
minimization on the reduced training set. This opposes common wisdom in
learning theory, where the expected error is supposed to decrease as the
dataset grows in size. In this work, we leverage extreme value theory to
address this apparent contradiction. Our results show that the tails of the
data distribution play an important role in determining the
worst-group-accuracy of linear classifiers. When learning on data with heavy
tails, throwing away data restores the geometric symmetry of the resulting
classifier, and therefore improves its worst-group generalization.
