Label-Imbalanced and Group-Sensitive Classification under Overparameterization

The goal in label-imbalanced and group-sensitive classification is to\noptimize relevant metrics such as balanced error and equal opportunity.\nClassical methods, such as weighted cross-entropy, fail when training deep nets\nto the terminal phase of training (TPT), that is training beyond zero training\nerror. This observation has motivated recent flurry of activity in developing\nheuristic alternatives following the intuitive mechanism of promoting larger\nmargin for minorities. In contrast to previous heuristics, we follow a\nprincipled analysis explaining how different loss adjustments affect margins.\nFirst, we prove that for all linear classifiers trained in TPT, it is necessary\nto introduce multiplicative, rather than additive, logit adjustments so that\nthe interclass margins change appropriately. To show this, we discover a\nconnection of the multiplicative CE modification to the cost-sensitive\nsupport-vector machines. Perhaps counterintuitively, we also find that, at the\nstart of training, the same multiplicative weights can actually harm the\nminority classes. Thus, while additive adjustments are ineffective in the TPT,\nwe show that they can speed up convergence by countering the initial negative\neffect of the multiplicative weights. Motivated by these findings, we formulate\nthe vector-scaling (VS) loss, that captures existing techniques as special\ncases. Moreover, we introduce a natural extension of the VS-loss to\ngroup-sensitive classification, thus treating the two common types of\nimbalances (label/group) in a unifying way. Importantly, our experiments on\nstate-of-the-art datasets are fully consistent with our theoretical insights\nand confirm the superior performance of our algorithms. Finally, for imbalanced\nGaussian-mixtures data, we perform a generalization analysis, revealing\ntradeoffs between balanced / standard error and equal opportunity.\n