Is Importance Weighting Incompatible with Interpolating Classifiers?
  Importance weighting is a classic technique to handle distribution shifts.
However, prior work has presented strong empirical and theoretical evidence
demonstrating that importance weights can have little to no effect on
overparameterized neural networks. Is importance weighting truly incompatible
with the training of overparameterized neural networks? Our paper answers this
in the negative. We show that importance weighting fails not because of the
overparameterization, but instead, as a result of using exponentially-tailed
losses like the logistic or cross-entropy loss. As a remedy, we show that
polynomially-tailed losses restore the effects of importance reweighting in
correcting distribution shift in overparameterized models. We characterize the
behavior of gradient descent on importance weighted polynomially-tailed losses
with overparameterized linear models, and theoretically demonstrate the
advantage of using polynomially-tailed losses in a label shift setting.
Surprisingly, our theory shows that using weights that are obtained by
exponentiating the classical unbiased importance weights can improve
performance. Finally, we demonstrate the practical value of our analysis with
neural network experiments on a subpopulation shift and a label shift dataset.
When reweighted, our loss function can outperform reweighted cross-entropy by
as much as 9% in test accuracy. Our loss function also gives test accuracies
comparable to, or even exceeding, well-tuned state-of-the-art methods for
correcting distribution shifts.
