You will be presented with the title and body text of a computer science research paper. Please write a summary of the work that would be informative for a peer reviewer assessing its quality. Your summary should be 10 sentences long. In your response, include only the summary and no additional text.

Paper title:
Is Importance Weighting Incompatible with Interpolating Classifiers?

Paper body:
1 INTRODUCTION . Machine learning models are often evaluated on test data which differs from the data that they were trained on . A classic statistical technique to combat such distribution shift is to importance weight the loss function during training ( Shimodaira , 2000 ) . This procedure upweights points in the training data that are more likely to appear in the test data and downweights ones that are less likely . The reweighted training loss is an unbiased estimator of the test loss and can be minimized by standard algorithms , resulting in a simple and general procedure to address distribution shift . Surprisingly , recent papers ( Byrd & Lipton , 2019 ; Xu et al. , 2020 ) have found that importance weighting is ineffective in the current deep learning paradigm , where overparameterized models interpolate the training data or have vanishingly small train loss . In particular , Byrd & Lipton ( 2019 ) empirically showed that when no regularization is used , overparameterized linear and nonlinear models trained with the importance weighted cross-entropy loss ignore the importance weights . Xu et al . ( 2020 ) followed up and provided a theoretical justification for this observation in overparameterized linear and non-linear models . To build intuition about why importance weighting fails , consider linear classifiers as an example . Given linearly separable data ( x1 , y1 ) , . . . , ( xn , yn ) ∈ Rd × { −1 , 1 } , Soudry et al . ( 2018 ) showed that if gradient descent is applied to minimize an exponentially-tailed classification loss ( ∑ i∈ [ n ] ` exp ( yixi ) ) then the iterates converge in direction to the maximum margin classifier θ̂MM : = arg min‖θ‖=1 { γ : yixi · θ ≥ γ , for all i ∈ [ n ] } . Xu et al . ( 2020 ) showed that in this same setting , minimizing the importance weighted loss ( ∑ i∈ [ n ] wi ` exp ( yixi ) ) with gradient descent also results in convergence to the maximum margin classifier , regardless of the weights . To see why , consider the special case where the weights ( w1 , . . . , wn ) are positive integers . This reweighting is equivalent to simply repeating each datapoint wi times , and the maximum margin classifier over this “ new dataset ” remains unchanged . Thus , invoking the original result by Soudry et al . ( 2018 ) proves that the importance weights has no effect in correcting the distribution shift . This result can be seen in Figure 1 where we demonstrate this phenomenon in a simple toy problem . Such evidence has led some to wonder if importance weighting is fundamentally incompatible with overparameterized interpolating models . In this paper , we show that this is not the case . We find that the culprit behind the ineffectiveness of importance weighting is the exponential tail of popular losses such as the cross-entropy or the logistic . We propose altering the structure of the loss to have fatter , polynomially decaying tails instead . We theoretically and empirically demonstrate that importance weights do correct for distribution shift under such losses even for overparameterized classifiers . Our first contribution is to characterize the limiting direction of the iterates of gradient descent ( its implicit bias ) when minimizing reweighted polynomially-tailed losses with linear classifiers . We show that this limiting direction is a function of both the datapoints as well as the importance weights , unlike the maximum margin classifier that only depends on the data ( see the right half of Figure 1 ) . Next , we analyze the generalization behavior of this classifier in a label shift setting . We prove that when the weights are an exponentiation of the unbiased importance weights , the test error decays to zero in the large sample limit , regardless of the level of imbalance in the data . In contrast , we prove that the test error of the maximum margin classifier in this same setting must be at least 1/8 . Finally , we demonstrate the practical benefits of our framework by applying this approach to experiments with neural networks . In both a label shift dataset ( Imbalanced Binary CIFAR10 ) , and a subpopulation shift dataset with spurious correlations ( CelebA ( Sagawa et al. , 2019 ) ) , we find that using polynomially-tailed losses consistently leads to a gain of 2-3 % in test accuracy over using the cross-entropy loss . 2 RELATED WORK . Early work ( Shimodaira , 2000 ; Wen et al. , 2014 ) already warned against the potential ineffectiveness of importance weights on interpolating overparameterized models . Shimodaira ( 2000 ) showed that when the model is well-specified , importance weights can fail to have an effect , and that the ordinary maximum likelihood estimate is asymptotically optimal . Wen et al . ( 2014 ) showed that when there is a zero-loss minimizer of an unweighted convex loss minimization problem , then it is also a minimizer of the ( adversarially ) reweighted loss as well . Recent work ( Byrd & Lipton , 2019 ; Xu et al. , 2020 ) has shown that importance weighting fails to have an effect on neural networks trained with gradient descent , though always in the setting of exponentially-tailed losses . Sagawa et al . ( 2019 ) demonstrated that reweighting can fail to have the desired effect when unregularized distributionally robust optimization ( DRO ) methods are used in conjunction with the cross-entropy loss . They empirically showed that regularization is necessary to reap the benefits of reweighting , also observed by Byrd & Lipton ( 2019 ) . Our work also connects to literature that has studied the implicit bias of gradient descent ( Soudry et al. , 2018 ; Ji & Telgarsky , 2019 ; Nacson et al. , 2019 ) . Especially relevant is the work by Ji et al . ( 2020 ) who relate the implicit bias of gradient descent with exponentially and polynomially-tailed losses for linear classifiers to a solution of a regularized loss minimization problem . Finally , our generalization analysis draws from the growing literature focused on finite sample bounds on the test error of the maximum margin classifier in the overparameterized regime ( Chatterji & Long , 2021 ; Muthukumar et al. , 2020 ; Wang & Thrampoulidis , 2021 ; Cao et al. , 2021 ) . 3 SETTING . We consider a distribution shift setting where the training samples { ( x1 , y1 ) , . . . , ( xn , yn ) } ∈ Rd × { −1 , 1 } are drawn i.i.d . from Ptrain , and the test samples are drawn from a different distribution Ptest that is absolutely continuous with respect to Ptrain . Let fθ denote a classifier parameterized by θ . Given a feature x , a classifier maps this feature to fθ ( x ) ∈ R. In this paper we shall consider cases where the classifier is either linear ( for our theory ) or a neural network ( for our experiments ) . Our goal is to find a classifier fθ that minimizes the 0-1 loss with respect to the test distribution : TestError [ fθ ] = P ( x , y ) ∼Ptest [ sign ( fθ ( x ) ) 6= y ] . To handle the mismatch between Ptrain and Ptest , we shall study importance weighting algorithms . Given a datapoint ( x , y ) ∈ Rd× { −1 , 1 } , the classical unbiased importance weight at this datapoint is given by the ratio of densities between the test and the train distributions Ptest ( x , y ) Ptrain ( x , y ) . Using these unbiased importance weights ensure that the reweighted training loss is an unbiased estimate of the test loss . However , as noted above , past work has shown that interpolating classifiers trained with gradient descent on importance weighted exponentially-tailed losses , such as the logistic loss ` log ( z ) : = log ( 1 + exp ( −z ) ) , the exponential loss ` exp ( z ) : = exp ( −z ) , and the cross-entropy loss , ignore the importance weights . For example , consider the case when the classifier is linear fθ ( x ) = x · θ , the weights are w1 , . . . , wn > 0 , and the reweighted loss function is L̂ ( θ ) = ∑n i=1 wi ` log ( yixi · θ ) . Xu et al . ( 2020 ) showed that if the data is linearly separable then the iterates of gradient descent converge in direction to the ` 2-maximum margin classifier , θ̂MM : = arg max θ : ‖θ2‖=1 { γ : yixi · θ ≥ γ for all i ∈ [ n ] } . ( 1 ) Observe that the maximum margin classifier does not depend on the set of importance weights ( w1 , . . . , wn ) and hence may suffer large test error when there is distribution shift . Xu et al . ( 2020 ) further showed that when separability assumptions hold , non-linear classifiers ( like multilayer neural networks ) trained with gradient descent on exponentially-tailed losses are also unaffected by importance weights . We initiate a study of polynomially-tailed losses in the distribution shift setting and show that they have improved behavior with respect to importance weighting even when the model is overparameterized . Given parameters α > 0 and β ∈ R define the polynomially-tailed loss as follows : ` α , β ( z ) : = { ` left ( z ) if z < β 1 [ z− ( β−1 ) ] α if z ≥ β , where ` left is any loss function such that the overall loss function ` α , β is convex , differentiable and strictly decreasing . Several natural choices for ` left include the scaled logistic ( c1 log ( 1 + exp ( −c2z ) ) ) , exponential ( c1 exp ( −c2z ) ) or linear ( −c1z + c2 ) losses . Given a training dataset { ( x1 , y1 ) , . . . , ( xn , yn ) } and a set of weights w1 , . . . , wn ≥ 0 we let L̂α , β ( fθ ) : = n∑ i=1 wi ` α , β ( yifθ ( xi ) ) be the reweighted empirical loss on this dataset . Notation . Given a vector v , let ‖v‖ denote its Euclidean norm . For any j ∈ N , we denote the set { 1 , . . . , j } by [ j ] . A random variable ξ is 1-sub-Gaussian if for any λ ∈ R , E [ eλξ ] ≤ eλ2/2 . 4 THEORETICAL RESULTS . In this section , we present several theoretical results that justify the use of polynomially-tailed losses in conjunction with importance weights to handle distribution shifts . To let the analysis proceed , we restrict our theoretical study to linear classifiers , fθ ( x ) = x · θ , for some θ ∈ Rd . First , in Section 4.1 we shall characterize the limiting direction of gradient descent on reweighted polynomially-tailed losses and show that this direction depends on both the weights as well as the datapoints . Next , in Section 4.2 , we upper bound the test error of this limiting solution in a label shift setting . We also show that choosing weights that are obtained by exponentiating the unbiased importance weights helps in reducing the test error . Finally , in this label shift setting , we show that the maximum margin classifier suffers an error that is at least 1/8 .

10-sentence paper summary:
Previous works pointed out an interesting incompatibility between importance sampling and training overparameterized neural nets. In the view of margin, Soudry et al. (2018) showed that GD on exponentially-tailed loss converges to the max-margin classifier, and Xu et al. (2020) pointed out that this margin maximization is unaffected by importance sampling. This paper then turns to studying polynomially-tailed loss.  * This paper establishes the implicit bias by formulating an optimization problem, which can change according to the importance weights. The convergent classifier is shown to generalize better than the exponentially-tailed loss in a simple linear classification setting, where the dataset contains two sub-Gaussian clusters. * Experiments on Imbalanced Binary CIFAR10 and CelebA show that the polynomially-tailed loss performs better on imbalanced datasets.