Is Importance Weighting Incompatible with Interpolating Classifiers?
Authors: Ke Alexander Wang
Niladri Shekhar Chatterji
Saminul Haque
Tatsunori Hashimoto
Venue: ICLR 2022 Poster (2022)
Keywords: overparameterization
distribution shifts
importance weighting
implicit bias
generalization analysis
interpolation

Abstract: 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. \emph{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.

Published as a conference paper at ICLR 2022
Is IMPORTANCE WEIGHTING INCOMPATIBLE WITH IN- TERPOLATING CLASSIFIERS?
Ke Alexander Wang', Niladri S. Chatterji", Saminul Haque, Tatsunori Hashimoto
Department of Computer Science Stanford University falxwang, niladr i cscs .tt.es..aatttttee stanford. edu, fsaminulh, thasshi]estanffodd.
ABSTRACT
Importance weighting is classic technique to handle distribution shifts. How- ever, prior work has presented strong empirical and theoretical evidence demon- strating that importance weights can have little 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 result of using exponentially-taiee entropy loss. As a remedy, we show that polynomially-tailen losses restore the effects of importance reweighting in correcting distribution shift in overparame- terized models. We characterize the behavior of gradient descent importance weighted polynomially-tailer losses with overparameterized linear models, and losses in
effect overparameterized
losses like the logistic or cross-
theoretically demonstrate the advantage of using polynomially-taie label shift setting. Surprisingly, our theory shows that using weights that are ob- tained by exponentiating the classical unbiased importance weights can improve performance. Finally, we demonstrate the practical value our analysis with neural network experiments on subpopulation shift and 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 com- parable to, or even exceeding, well-tuned state-of fate--oftte--e art methods for correcting distribution shifts.
INTRODUCTION
Machine learning models are often evaluated on test data which differs from the data that they were trained 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 more likely 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 address distribution shift.
Surprisingly, recent papers (Byrd & Lipton 2019 Xu et al.] (2200) have found that importance weighting is ineffective in the current deep learning paradigm, where overparameterizee models terpolate the training data or have vanishingly small train loss. In particular, |yrdd & 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 theoretical justification for this observation in overparame- terized linear and non-linear models.
To build intuition about why importance weighting fails, consider linear classifiers as an exam plc. Given linearly separable data (21, (In, Vn) E dd x {-1, Soudry et al. (2018) showed that gradient descent is applied to minimize an exponentially-taile classification loss (Erejn) fexp (y,,.)) then the iterates converge in direction to the maximum margin classifier ŪMM == arg min tr y:44 0 2 7, for all E [n]].. Xu et al. (2020) showed that in this same setting, minimizing the importance weighted loss (Eie(n) wypeep ():))) with gradient descent also results
"qqual contribution.

---

Published as a conference paper at ICLR 2022
Cross Entropy: No IW
Cross Entropy: IW
Poly-tailed Loss: No IW
Poly-tailed Loss: IW
As
As
de de
as
di
Learned Boundary
Prodicted Majority
Majority Class
True Boundary
Prodictod Minority
Minority Class
Figure I: Models trained with gradient descent, with and without importance weights (IW), in the label shift setting where classes are imbalanced in the training set. All models interpolate the training points with 100% accuracy. (Left) Importance weights provably fails to correct for the distribution shift for the cross-entropy loss. The learned boundary is asymptotically the maximum- margin classifier with reweighting. (Right) Our polynomially-tailee loss restores the effects of importance weights, correctly adjusting for the distribution shift.
in convergence to the maximum margin classifier, regardless of the weights. To see why, consider the special case where the weights (Wa,..., W,) are positive integers. This reweighting is equiva- lent to simply repeating each datapoint w, times, and the maximum margin classifier over this "new dataset" remains unchanged. Thus, invoking the original result by [Soudry al. (2018) proves that the importance weights has no effect in correcting the distribution shift. This result can be seen in Figure 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 the loss to have fatter, polynomially decaying tails instead. We theoretically and empirically show that importance weights do correct for distribution shift under such losses even for overparameterizee classifiers.
Our first contribution is to characterize the limiting direction of the iterates of gradient descent (its implicit bias) when minimizing reweighted polynomially- We show that this limiting direction is function of both the datapoints well the importance weights, unlike the maximum margin classifier that only depends on the data (see the right half of Figure Next, we analyze the generalization behavior of this classifier in 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 maximum margin classifier test error in this same setting must be at least 1/8.
losses with linear classifiers.
Finally, we demonstrate the practical benefits of our framework by applying this approach to ex- periments with neural networks. In both label shift dataset (imbalanced binary CIFARIO) 10), and subpopulation shift dataset with spurious correlations (CelebA (Sagawa al. 2019)), we find that reweighting polynomially-tailed losses consistently outperforms reweighted cross-entropy loss, as our linear theory suggests. Additionally, poly-tailed loss with biased importance weights can per- form comparably to, better than, state-of-the-as methods distribution shift (Cao et al. 2019 Ye
ctt al. 2020, Menon et al. 2020 Kini et al. 2021
RELATED WORK
Early work (Shimodairal 2000 Wen et al.) 2014) already warned against the potential ineffective- ness 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 al. (2014) showed that when there is zero-loss minimizer of an unweighted convex loss minimization problem. then it is also a minimizer of the (adversarially) reweighted loss well. Recent work (Byrd & Lipton 2019
Xu et al. 2020) has shown that importance weighting fails to have an effect on neural networks
"Code available htwp://wwwwn.n.ooeeeeeeeeeeeeeee

---

Published as a conference paper at ICLR 2022
trained with gradient descent, though always in the setting of exponentially-taibe losses. Sagawa et al. (0119) 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 2
A recent line of work (Cao et al. 2019 Ye et al., 2020; Menon et al. 2020: Kini et al., 2021 has
introduced modifications to the logistic and cross-entropy losses to correct for distribution shift. Cao et al. (2019) and Menon et al. (2020) proposed using additive corrections to the logits. However, without regularization or carly-stopping these corrections are ineffective since the additive correc- tions to the logits is analogous to importance weighting exponential-tailed losses. Multiplicative logit corrections (Ye et al.] 2020), possibly combined with additive corrections (Kini et al.) (021), have also been proposed. Unlike the additive conrections, these methods do not converge to the max-margin classifier, but they also do not correspond to importance weighting algorithms. In our work, we focus on the question of whether importance weighting alone can correct for distribution shift, and show practical empirical benefits relative to multiplicative logit corrections.
Our work also connects to literature that has studied the implicit bias of gradient descent (Soudry iet al. 2018 Ji & Telgarsky 2019 Nacson et al. 2019). Especially relevant is the work by Ji et al. (220 who relate the implicit bias of gradient descent with exponentially and polynomially-taiie losses for linear classifiers to solution of 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 overparameterizee regime (Chatterji & Long. Cao et al. 2021).
2021 Muthukumar et al., 2021. Wang & Thrampoulidis) 202T
SETTING
We consider a distribution shift setting where the training samples (1),,1),... vi)..., (In, Ho)} } Rd x {-1, }} are drawn i.i.d. from Ptrain: and the test samples are drawn from a different distribution Prest that is absolutely continuous with respect to Ptrain- Let fe denote classifier parameterized by 0. Given a feature æ, a classifier maps this feature to fe() E IR. In this paper we shall consider cases where the classifier is either linear (for our theory) or a neural network (for experiments).
Our goal is to find a classifier fo that minimizes the 0-1 loss with respect to the test distribution: TestError (x..)))>Pe (sign(fo(z)) # v]
To handle the mismatch between Ptrain and Ptest we shall study importance weighting algorithms. Given datapoint v) E Rd {-1, 1}. the classical unbiased importance weight at (z, y) is given by the ratio of densities between the test and the train distributions Pa (2.y) Pezin (x..)) Using these unbiased importance weights ensures 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 losses (such as the logistic loss (lg(2) :=
descent on importance weighted exponentially-tailee log (1 + exp(-2)), the exponential loss (exp(=) exp(-2), and the cross-entropy loss) ignore the importance weights. For example, consider the case when the classifier is linear fo(x) = x 0, the weights are Wi. Wnn > O, and the reweighted loss function is L()) Σi=1 Welhog (y:z4 0). Xu et al. (2020) showed that the data is linearly separable then the iterates of gradient descent converge in direction to the fg-maximum margin classifier,
ŌMM = arg max {T your 0 2 7 for all i [n]]]
9: 0:10211==1
Observe that the maximum margin classifier does not depend on the importance weights (wi...., W,, 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 trained with gradient descent exponentially-tailee losses are also unaffected by importance weights.
We initiate a study of polynomially-taiie have improved behavior with respect to importance weighting even when the model is overparame- terized. Given parameters a > 0 and 3 e R define the polynomially-tailee loss as follows:
losses in the distribution shift setting and show that they
(x, = (lett
if = < /
if 2 8
33-(0
11-1"
3

---

Published as a conference paper at ICLR 2022
where fiett any loss function such that the overall loss function L convex. differentiable and strictly decreasing, Several natural choices for Leett include the scaled logistic (ci log(1= + exp(-c2=))), exponential (c1 exp(-c22) linear (-c12 + c2) losses.
Given a training dataset {(11, (Inz and a set of weights w1. wi.... Un 2 we let
L (So)
Σ w o
be the reweighted empirical loss on this dataset.
Notation. Given vector let ||a|| denote its Euclidean norm. For any j E N, we denote the set (). by [j]. A random variable is 1-sub-Gaussian if for any R, E [e>e] ex//2
4 THEORETICAL RESULTS
In this section, we present several theoretical results that justify the use of polynomially-taile losses in conjunction with importance weights to handle distribution shifts. Our final result shows strict separation between the performance of reweighted polynomially- and explonentially-taile under label shift. We restrict our theoretical analysis to linear classifiers, fo(x) = x . 0, for some 0 E IRd.
models
First, in Section 4.1 we shall characterize the limiting direction gradient descent on reweighted polymomially-tailed losses and show that this direction depends 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.
4.1 IMPLICIT BIAS OF GRADIENT DESCENT POLYNOMIALLY TAILLD LOSSES
We begin by presenting result that characterizes the implicit bias of gradient descent on reweighted polynomially-tuine losses for linearly separable classification. Understanding this situation is a key first step, gradient descent for separable linear classification is often used as a simplified model to theoretically characterize the behavior overparameterized neural networks (Soudry et al. 2018
Ji & Telgarsky 2019 Nacson al. 2019 Lyu & Li 2019 Ji & Telgarsky 2020).
Given a linearly separable dataset (#1, V1).................... (In, Vn), we let 24 == y:zz- We shall analyze the iterates of gradient descent with step-size > and initial iterate g(0) e Rd, for all t e {0, I....::
1(++1) = ((t) v/Vi (((()))(()) Define the direction
0. = arg min 0:1|011=1
WG
S.L.
zi 00000
for all i [n]
0)aa
The following proposition characterizes the limiting direction of gradient descent iterates.
Proposition 4.1. Suppose that the data linearly separable. For any a > O, 3 R, any initial point (()) E Rdd and for all small enough step-sizes the direction of the gradient descent iterates
satisfy the following: lim;-
g()
0g.
The proof is presented in Appendix This proof relies recent result by Ji et al. (200)) that relates the limiting direction of gradient descent the unregularized loss the limiting solution norm- constrained loss minimization problem, where the limit is taken with respect to the norm constraint.
Note that, unlike the maximum margin classifier, it immediately clear that this limiting direction 8_ depends on the weights W1,- Wn. As one would intuitively expect, the direction 8, tries to achieve larger margin 9 on points with larger weights w;- This behavior is also apparent in the simulation in the rightmost panel in Figure I where upweighting points the minority class helps to learn classifier that is similar in direction the Bayes optimal classifier for the problem.
Our limiting direction 0₂ has the interesting property that it does not depend on several quantities: the initial point ((0) the properties of fee and the "switchover" point Linear separability ensures
4

---

Published as a conference paper at ICLR 2022
that in the limit, the margin on each point much larger than B, and so the loss of each point is in the polynomial tail of part of la,p.
4.2 GENERALIZATION ANALYSIS
The result in the previous subsection shows that the asymptotic classifier learnt by gradient descent, On respects importance weights. However, this does not demonstrate that using polynomially-taiae losses leads to classifiers with lower test error compared to using exponentially-taieed losses.
To answer this more fine- fine-grained question, we will need to perform a more refined analysis. To do this we will make sub-Gaussian cluster assumptions on the data, similar to ones considered in the generalization analysis of the overparameterized maximum margin classifiers (Chatterji & Long.
Wang & Thrampoulidis: 2021 Liang & Recht 2021 Cao al. (021). In our setting, the features associated with each label are drawn from two different sub-Gaussian clusters. We shall consider a label shift problem where the training data is such that the number of data points from the positive (majority) cluster will be much larger than the number of datapoints from the negative (minority) cluster. The test datapoints will be drawn uniformly from either cluster.
2021
Under these assumptions, we derive upper bounds on the error incurred by 0,, the limiting direction of gradient descent of polynomially tailed losses with = 1 (Section 4.2.2). We will find that its test error is small when the reweighting weights are set to cubic powers of the unbiased importance weights. (A similar analysis can also be conducted for other o.) In the same setting in Section 4.2.3 we will show that the maximum margin classifier must suffer large test errors.
4.2.1 1 SETTING FOR GENERALIZATION ANALYSIS
Here formally describe the setting of our generalization analysis. We let C 2 and < Č < denote positive absolute constants, whose value is fixed throughout the remainder of the paper. We will use c, c1, denote "local" positive constants, which may take different values in different contexts.
The training dataset S : (x11 91), ...,, (In, yn)} has independently drawn samples. The condi- tional distribution of the features given the label is
x {u = 1] 1 Uq
-y= +Uq
where in /22 = 0, / || = || U is an arbitrary orthogonal matrix, and q is a random variable such that: its entries are
and independent, and E [[[a]]]] 2 Cd..
We note that past work that studied this setting (Chatterji Long 2021 Wang Thrampoulidis 2021 Cao et al. 2021), the cluster centers were chosen to be opposite one another Jr -/22- Here, since our goal here is to study label shift setting we consider the cluster centers μ4 and μ2 to be orthogonal. This ensures that learning the direction of one of the centers reveals no information about the other center, which makes this problem more challenging in this setting.
Define P = {i [n] : y, = 1} to be the set of indices corresponding to the positive labels and N : {i E [m] y: -11 11 to be the set indices corresponding to the negative labels. As stated above, we will focus on the case where [P| > |M| 2 1. Let
DVT > 1 be the ratio between [P]
the number of positive and negative samples. The test distribution Pest is balanced. That is, if (r, ~ Prest- then IP jy = Ply = -1] = 1/2 and x follows the distribution as described above. We shall study the case where negative examples (which are in the minority) are upweighted. Specifically, set the importance weights as follows: wt = 1 for E P and uq w for i e N.
Assumptions. Given failure probability 0 < 1/C, we make the following assumptions on the parameters of the problem:
1. Number of samples n 2 C Clg((1/)).
2. Norm of the means || |u||2= : || 2 = || > Cn² log(/))
3. Dimension d 2 Cn]]u||2
Our assumptions allow for large overparameterization, where the dimension d scales polynomially with the number of samples
5

---

Published as a conference paper at ICLR 2022
4.2.2 UPPER BOUND FOR THE REWEIGHTED POLYNOMIALLY- TAILED LOSS CLASSIFIER
First, we shall prove an upper bound on the test error the solution learnt by gradient descent on the reweighted polynomially-taile loss. Under the choice of weights described above, by equation ?
0, arg min 0:1011=1
Σ TEP
Σ iEN
s.t. 2i - 0, for all E [x],
where z = yr as defined previously. The following theorem provides an upper bound on the test error of 81 and specifies range of values for the weight w.
Theorem 4.2. For any Č S 1, there is a constant such that, for all large enough C and for any 0 < 8 < 1/C, under the assumptions of this subsection the following holds. If the weight
S 2T then with probability at least ò, training on produces classifier O2 satisfying:
cn ||
TestError [i]] = P(a.)))-Pan sign (0,
S exp (-
This theorem is proved in Appendix B To prove this theorem, we first show that the data is linearly separable under assumptions and use the implicit bias results of Proposition 4.1 Then, our upper bound is equivalent to bounding the test error of the limiting iterate gradient descent on reweighted loss. Next, show that the sum of the gradients across each of the two groups remains roughly balanced throughout training under our choice of w. This ensures that the classifier aligns well with both cluster centers μ41 and =22 which then proves bound the test error via a standard Hoeffding bound.
If we consider regime where d and n are growing simultaneously. then the test error goes down to zero if the norm of the cluster means ||ك grows faster than d'/4, regardless of the level of imbalance in the training data as T < n. Briefly note that in setting with balanced data (r = 1), the bound on the test error here matches the bound obtained for the maximum margin elassifier in (Chatterji & Long 2021] Wang & Thrampoulidis [2021] Cao et al., (02T)) (although these bounds are not directly comparable the setting here slightly modified for label shift). The impossibility result by Jin (2009) shows that these previous results guarantee that learning occurs right up until the information theoretic frontier (I] = (()d).
Finally, it is interesting to note that the theorem requires the weight to scale with 7 instead of (the unbiased importance weight), which would ensure that the reweighted training loss is an unbiased estimate of the test loss. In our proof, we find that order to suffer low test error is important to guarantee that the norm of the gradients across the two groups is roughly balanced throughout training. We show that at any training iteration, the ratio of the sum of the derivative of the weighted losses in the majority and minority clusters scales as w//3 Thus choosing to scale with 3 ensures that the gradients are balanced across both groups. We verify this in simulations (Figure 2). and find that w 73 ensures equal test error across both classes, reducing overall error.
4.2.3 LOWER BOUND FOR THE MAXIMUM MARGIN CLASSIFIER
In the previous section we derived an upper bound to demonstrate that classifiers trained with polynomially-taile losses achieve low test error. We will now show that classifiers trained with exponentially-tailed losses have their error lower bounded by 1/8 in the same setting.
Theorem 4.3. Let q ~ N(O, Iaxa). There exist constants e and c' such that, for all large enough C and for any 0 < 8 < L/C, under the assumptions of this subsection the following holds. With probability least 8, training on produces a maximum margin classifier bMMm satisfying:
TestError (0wm) (().a)))PP [sign (Pham xx) +
cVn
||1]122) Vd
where & is the Gaussian edf. Furthermore, if the imbalance ratio 2 d' Vallell Va
then with probabil-
ity at least - 8. TestError(@wmll >
This theorem is proved in Appendix C Intuitively, the lower bound holds because when the imbal- ance severe, the max-margin classifier essentially ignores the samples in the minority class and

---

Published as a conference paper at ICLR 2022
Test Error Irballnce Ratio ir)
Test Ervor Importance Weight (w 57)
10
25
Majority Class
Minority Class
Test Erver (%)
Ted Ernr (g)
20
Owrrill
6
maargin
15
4
10
2
5
0
0
2
4
6
10
12
0
2
3
4
5
Imbullner: Ratio (r)
Figure 2: A simulation study with class-conditional Gaussians, with d 106, |||| d and n = -100. The mean μ4r = [|д][e] and μ12 - [|æ||ez, and q ~ N(0, laxa). (Left) We plot the test error of 0, as varies for different choices of w. and also for the maximum margin classifier. The choice w 7 leads the lowest error throughout, while w r also does well for small r. Both classifier with no importance weighting and the maximum margin classifier
the polynomially-taile suffer large test error. (Right) Here we fix the imbalance ratio т = 10.1, and study how the error of 0 varies with w. When w = 73, the error on both the majority and minority classes almost equal, resulting in low overall test error.
overfits to the majority class. Ignoring these negative samples results in relatively small alignment between the maximum margin classifier and the negative of the minority class center, which leads to high error on this class.
Together, these two theorems demonstrate that there is strict gap between the performance of exponentially tailed and polynomially tailed losses under distribution shifts. As a concrete example, consider the scaling where |||4|/ = d + कं n = dt and T = d < n. For all large enough d, all our assumptions are satisfied. Now since, v/| > Vrd, Theorem 4.2 guarantees that the test d 2 e'Ilui12 Vn/d d' d for all large enough d,
error of 0 + 0 as d co. However, the test error of the maximum margin classifter is guaranteed to be at least 1/8. This degradation of the test error with 7 is also apparent in our simulations in Figure 2
5 EMPIRICAL EVALUATION ON DEEP INTERPOLATING CLASSIFIERS
Inspired by our theoretical results, we use a polynomially-tailed loss with importance weights to train interpolating deep neural networks under distribution shift. We use polynomially-taile loss with 3 = 1 and (2) = log(1 + + log(1 + e)), ensuring that fa.9 is continuous at transition 3 when a 1. We train models on two image classification datasets, one with label shift and one with subpopulation shift, and include additional experiment details in Appendix E Though these nonlinear networks violate the assumptions our theory, polynomially-taie loss with importance weights consistently improves test accuracy for interpolating neural networks under distribution shift compared to importance-weiin weighted cross-entropy loss.
Imbalanced binary CIFAR1O. We construct our label shift dataset from the full CIFARIO dataset. Similar to Byrd & Lipton 2019), we create a binary classification dataset out of the "cat" and "dog" classes. We use the official test examples as our label-balanced test set of 1000 cats and 1000 dogs. To form the train and validation sets, we use all 5000 cat examples but only 500 dog examples from the official train set, corresponding to a 10:1 label imbalance. We then use 80% of those examples for training and the rest for validation. We use the same convolutional neural network architecture as Byrd & Lipton (2019) with random initializations for this dataset.
Subsampled CelebA. For our subpopulation shift dataset, we use the CelebA with spurious cor- relations dataset constructed by (Sagawa et al.] (2019). This dataset has two class labels, "blonde hair" and "dark hair". Distinguishing examples by the "male" versus "female" attribute results in four total subpopulations, or groups. The distribution shift in the dataset comes from the change in relative proportions among the groups between the train and test sets. To reduce computation, we train on 2% of the full CelebA training set, resulting in group sizes of 1446, 1308, 468, and 33. We construct test by downsampling the original test to get group-balanced representation in
7

---

Published as a conference paper at ICLR 2022
Trained to Interpolation
Iubelonncd Binary CIEARIO
Subesapplod CelebA
0.70
0.90
Prigetuledd Toos
0.65
Cruss Entrapy
*
Test Accuray
Trst Accurncy
0.85
0.60
0.55
0.80
0.50
0.75
0.45
0.40
0.70 No IW
No IW
IW (1))
IW (00213)
IW IW (w")
Figure 3: Polynomially-tailer loss versus cross-entropy loss on label shift dataset and a subpopu- lation shift dataset for neural networks optimized past 100% train accuracy without regularization. and ** indicate p < 0.05 and p < 0.005 statistical significance, respectively. Importance weights (IW) consistently leads to gains when used with the polynomially-tailed loss across both datasets. Exponentiating the weights further amplifies these gains for the polynomially-tailee loss. IW has little effect for cross-entropy
the test set, resulting in 180 examples for each group. Following Sagawa et al. (2019), we use a ResNet-50 with ImageNet initialization for this dataset.
5.1 ISOLATING THE EFFECTS OF IMPORTANCE WEIGHTS
Interpolating regime. To understand the impact of polynomial losses in the interpolating regime, we train unregularized neural networks with SGD past 100% train accuracy and report their final ac- curacies on the test sets. We compare models trained with our polynomially -aille loss against those trained with the cross-entropy loss which has exponential tails. Let w correspond to the unbiased importance weights. We consider three weighting scenarios for both loss functions: no importance weighting at all (No IW) the classical unbiased importance weighting (IW (w)), and biased weight- ing where exponentiate the weights, (IW (w")), increasing the ratio of different weights. The third setting is inspired by our theory in Section 4 that shows biased importance weights can im- prove performance for polynomially-talle the exponents to be the largest value that still allowed for stable optimization. For CelebA, we ex- ponentiate by 2 and for CIFARIO we exponentiate by 3/2. We run 10 seeds for each experiment setting. We compare the two losses via paired one-sided Welch's S (-tests, pairing runs with the same random seed. We report the exact numbers in Appendix B
losses. For these experiments,
fixed = 1 and set
Figure shows the mean accuracy and the standard error for each of the three settings. As indicated by our theory, we find that importance weighting with polynomially-tailed losses leads statisti- cally significant gains over cross- cross-entropy in all cases. Further we find that exponentiating weights boosts the performance of polynomially tailed losses, confirming our claims in Theorem 4.2] How- ever, exponentiating the weights leaves the performance of cross-entropy loss largely unchanged. In the case of CelebA we find that exponentiated reweighting with poly-tailed losses outperforms all other methods. While in the case of Imbalanced Binary CIFAR1O. 10, find a smaller gap between polynomially-taiie losses and cross-cntrope partially due to a substantially higher run-to-run vari- ability in training. This variability does not affect our main conclusion: exponentiated reweighting with poly-tailed losses still outperforms cross-entropy with significance p = 0.01.
In Appendix D also compare the performance of polynomially-taiin tailled losses with the cross- entropy loss when we regularize training via early-stopping. We find that even with regularization, poly-tailed losses give test accuracies better than similar cross-entropy across scenarios.
5.2 COMPARING AGAINST PRIOR DISTRIBUTION SHIFT METHODS
To place our method's empirical performance in the context of prior works, we extensively compare our method to tfate-of-the-ar distribution shift correction methods. On binary CIFAR1O, we com-
Thhe mean test accuracy for No IW with cross- entrroy on CIFARIO appears to deviate from IW, but this is due to the high variance across multiple runs of the model. The high variance arises due to 10:1 imbalanced training data, combined with the fact that we train the models until they interpolate the training data. These results for No IW differ slightly from those in Byrd & Lipton 2019) which used balanced training data and imbalanced test data.
8

---

Published as a conference paper at ICLR 2022
Imbbelaneed Binary CIFARIO
Suleamplee CelelAA
0.7
Test Accureyy
Test Acumayy
01.85
0.6
0.80
0.5
0.4
CE-US
LDAM
CDT
1. 1/5
Pub
CEACS
V8
Poly 1080
CEI DRR
VS-088
Figure 4: Polynomially-taie itive with state of the art methods that address distribution shift. We tune all methods extensively using the same validation set. We compare to cross entropy with undersampling (CE+UU), label- distribution-aware margin loss (I.AAM), class-dependent temperatures loss (CDT), logit-adjusted loss (LA), vector-scaling loss (VS), and the use of distributionally robust optimization (DRO).
loss with exponentiated importance weights is better than or compet-
pare to aubel-distribution--aaarr margin (LDAM) loss (Cao et al., 2019), class-dependent tempera- tures (CDT) loss (Ye et al. 2020). logit-adjusted (LA) loss (Menon et al. 2020), and scclorg (VS) loss (Kini et al., al.]2021) On CelebA, we compare to VS loss only since it encapsulates CDT
loss, LA loss, and LDAM loss. We also evaluate the effects of distributionally robust optimization (DRO) by [Sagawa et al. each method exhaustively, and report results over 10 random initialization seeds. See Appendix for more details on our procedure and the best hyperparameters we found. Unlike in Section [ here we tune both the importance weight exponent and a for our poly-tailed loss. For all methods, including ones that use DRO, we train all models to interpolation without early stopping or strong regularizations, since we are interested in interpolating classifiers.
2019) when combined with poly-tailed loss versus V$ loss. We grid search
E
Figure 4 shows that when a and the weights' exponent are properly tuned, our poly-tailed loss with exponentiated weights gives accuracies comparable to or even exceeding those by these recently proposed methods. For both datasets, we found that cross entropy (CE) loss with undersampling (US), which discards data from overrepresented groups or classes to form a balanced training set, was a strong baseline.
On binary CIFAR1O, our poly-tailed loss performs comparably to LA loss and only 2% worse than VS loss in mean test accuracy with overlapping confidence intervals. At first, grid searched VS loss across the published hyperparameter ranges from Kini et al. (202I). and it performed poorly (58.6% test accuracy). More thorough grid search for VS loss gave optimal hyperparameters that were similar to those of LA loss, increasing test accuracy by 10%. In sum, our poly-tailed loss matched or exceeded existing data imbalance adjustment methods (under published hyperparame- ters) and was beaten by 2% only after more extensively tuning the baselines.
On CelebA, our poly-tailed loss with IW achieves comparable test accuracy to VS loss. When we use both loss functions with DRO, poly loss with DRO is better than VS loss with DRO by 3.5% on test accuracy and 8% better on worst group accuracy. Poly-tailed loss with IW gives the best worst group accuracy out of all loss functions when not using DRO (see Appendix E.. Such improved performance surprising, as we designed polynomially tailed losses to optimize for static importance weights, rather than the worst case weights in DRO. The finding that tailed losses with IW performs well on worst-group accuracy may be an interesting direction for future work
CONCLUSION
Contrary to popular belief, importance weights are in fact compatible with the current paradigm of overparameterized classifiers, provided that the loss function does not decay exponentially. The limiting behavior of an interpolating linear classifier trained with a weighted polynomially-talled loss provably depends the importance weights, unlike the maximum-mann margin classifier recov- ered by an exponentially decaying loss function. Our theoretical analysis of generalization error further suggested that exponentiating the classic importance weights can be key to accurate distribu- tion shift correction. We empirically corroborated these theoretical intuitions, finding that weighted polynomially-taled losses are also able address distribution shift for interpolating neural net- works. Our work suggests that heavy-tailed losses together with importance weighting serve as a simple and general candidate for addressing distribution shift in deep learning.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
We use publicly available datasets in our paper, and do not foresee any potential harm arising from the use of our methods.
REPRODUCIBILITY STATEMENT
The full proofs of our theoretical results presented in the appendix. All experimental details and hyperparameters are presented in Appendix
REFERENCES
Brian Beavis and Ian Dobbs. Optimisation and stability theory for economic analysis. Cambridge University Press, 1990.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning, pp. 872-881, 2019.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribution-avy margin loss. Advances in Neural Information Processing Systems, pp. 1567-1578, 2019.
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over over-parameterized maximum mar-
gin classification on sub-Gaussian mixtures. arXiv preprint arXiv:2 10221114423385 13628, 2021.
Niladri Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129):1-30, 2021.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pp. 1772-1798, 2019.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In Advances in Neural Information Processing Systems, pp. 171866 2020.
Ziwei Ji, Miroslav Dudik, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pp. 2109-2136, 2020.
Jiashun Jin. Impossibility of successful classification when useful features rare and weak. Pro- ceedings of the National Academy of Sciences, 106(22)88859-855) 2009.
Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak, and Christos Thrampoulidis. Label-imbalanced and sooup-eensitive classification under overparameterizaaton. arXiv preprint arXiv:2103.01550, 2021.
Tengyuan Liang and Benjamin Recht. Interpolating classifiers make few mistakes, arXiv preprint arXiv:2101.1 11155, 2021.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations, 2020.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22(222):1-69, 2021.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In Conference on Artificial Intelligence and Statistics, pp. 3420-3428, 2019.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. arXiv preprint arXiv: 11119/11000 108731, 2019.
10

---

Published as a conference paper at ICLR 2022
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference, 90(2):227-244, 2000.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, 2018.
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of Gaussian mix- tures. IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 4030- 4034, 2021.
Junfeng Wen, Chun-Nam Yu, and Russell Greiner. Robust learning under uncertain test distribu- tions: Relating covariate shift to model misspecification. In International Conference on Machine Learning, pp. 631 631-639, 2014.
Da Xu, Yuting Ye, and Chuanwei Ruan. Understanding the role of importance weighting for deep learning. International Conference on Learning Representations, 2020.
Han-Jia Ye, Hong- You Chen, De-Chuan Zhan, and Wei-Lun Chao. Identifying and compensating for feature deviation in imbalanced deep learning. arXiv preprint wrXiv:2001.01385 2020.

---

Published as a conference paper at ICLR 2022
A PROOF OF PROPOSITION 4.
First, we restate the statement of the proposition.
Proposition 4.1. Suppose that the data linearly separable. For any a > 0, 3 R, any initial point (10) E Rd and for all small enough step-sizes the direction of the gradient descent iterates
satisfy the following: lim,->o [6008] 0a.
(9)
Proof Recall that the loss fa, is assumed to be convex, strictly decreasing to zero and is differen- tiable. Define the minimizer of the loss over ball of radius follows
OR = arg min Lo,,(().
0:110 SS
Under the assumptions of this proposition, we can invoke Theorem by Ji et al. (2020) to get that
g(0)
OR R
lim
lim R-+00
We will therefore instead demonstrate that lim
On H
0~ establish our claim.
First, note that the classifier On is the minimizer of loss a ball of radius R, so there exists a Ro with
(0Ro(O
Σ wila,ol2 0R)) S " (min (E(m)
such that for all Ro, each example classified correctly by 0n and the margin (2; (n) on each example is at least B. Therefore,
(On) Σ ula 0n)
1x OR (B 1)
Thus, for any radius > Ry we have
arg min (()
R
R 0:
Wi
arg min
s.t. 24 2
R o:
(3
1)] a+
arg min R
wi
(8) s.t, 2j
2 R
0:11011S
N
0
8-1
77
x
R. arg min
s.t., 2i 02 #
R
0:101111
2i
8-1
n
Now taking the limit R + oo get that
PR lim arg min
W1
lim
S.L, 2, 0 π
R
R
R oillelss
3-1
24
arg min
lim R-+00
W/
s.t., 24 0 g
0:100||11
1=1
24
8-1
R
Wi
arg min
S.L, 2, 0200
(2) 0)ai
0: 0:100||:1
Wi
arg min A:[|||i1
s.t. 2 .0>0
(z: 0)a
0
12

---

Published as a conference paper at ICLR 2022
where (i) follows since for every R the function
Wi
9-1
is convex and continuous, and therefore
W;
arg min 0:
S.L. 2 fi
9-1
21
has unique minimizer (since the objective function is strictly convex, and the constraint set is convex and compact), and is continuous map by Berge's maximum theorem (see, e.g., Beavis & Dobbs, 1990, Theorem 3.6). Thus, is possible to switch the order of limit and the arg min. Equation (aa) follows since the data is linearly separable, there exists 0 such that 0 > 0 for all i which has finite objective value.
Therefore,
(
On
lim t000
lim R
0.
|
R
which finishes our proof.
B PROOF OF THEOREM 4.2
In this section, we will prove an upper bound on the test error oj. which is the classifier learnt by gradient descent with the importance weighted Polynomially-taile Proposition 4.1, we know the choice of bee and 3 does not affect the implicit bias of gradient descent, hence here, for the sake of convenience, we shall use the specific loss function
loss that decays as 1/2. By
if B
(,a(2)= ==
i B,
(8-18-
with 3 1- wn 0. can be easily checked that this loss function is convex, differentiable and monotonically decreasing.
We want to bound the test error of 0,, however, in light of Proposition 4.1 we will instead bound
the test eтror of the limiting iterate of gradient descent starting from ((0) Sw2/3n (Hr - w 1/3 p2) with step-size 7 > (again by the implicit bias of gradient descent affected by the choice of the initial point):
g(++)) = git) - -7Ti(((0))
where
I(0) = Σ (z. +)+ w Σ (1,0(zi-)) 0).
iEP
VE.N
Recall that if the step-size is small enough then Proposition 4.1 guarantees that lim4 git)
[[01)] 0
In this section we will simply let l denote 1, and also use the shorthands e(t) = f(2z ((+)) and ((()) = f(;; (()).
With this setup in place let us begin the proof. All of the assumptions made in Section 4.2.1 are in scope here. First we have lemma that upper bounds the test error using Hoeffding's 's inequality.
Lemma B.I. There is a positive absolute constant such that
exp -c (0 22)
-c (0
(0 u22 )
P Playy)PPnn (sig (0 x) +
v 2
+ exp
1011
1012
13

---

Published as a conference paper at ICLR 2022
This lemma follows by mirroring the proof of (Chatterji & Long 2021 Lemma 9) which in turn follows by simple application of Hoeffding's inequality (Vershynin 2018 Theorem 2.6.3).
Next have lemma that proves bounds on the norms of the samples, bounds the inner products between the samples and also shows that with high probability the data is linearly separable.
Recall that the constants C 2 1 and O < S 1 were defined above in Section 4.2
Lemma B.2. For all O < C < 1, there is a e 2 1 such that, for all large enough C, with probability
1 8 over the draw of the samples the following events simultaneously occur:
1. For all E [n]
d S 1 12 S cd.
2. For all i E E and j E N,
z 2Y1 S ov dlog(n//).
3. For all i i [m]]
1 :2. < <Claall + /log(n//)).
4. For all E P,
114 -2 - - < ||a|1/ 1/2
5. For all N,
(--2)) 2k - 11111111 < //2
6. For all N,
111 - 2ul < cl1ا|| Vlogn/88).
7. For all E P,
1 2d < c||m|| Vlog(n/8).
8. The samples are linearly separable.
Proof We shall prove that each of the ten parts hold with probability at least 1 5/10 and take
union bound to prove our lemma. Under the assumptions of this lemma, Parts (T) (3) (5) and (8) can
be shown to hold with the required probability by invoking (Chatterji & Long 202T Lemma 13). We will show that Parts (2). (6) and (7) also hold with the required probability to complete the proof.
Proof of Part 2 Note that for all i E P. 24 A1 Uq, and for all i E N, 2 122 + Uq2- Therefore, for any E P and j E N, since
= 0,
1 231 = P1 (Ugz) + P22 (Uq:) + qi
S 1pn (Ugz)) ) + 1M2 (Uq+) |q: gzl
I(UT (1) 11 10 P2) q:1 [g: 4/-
(3)
We will show that each of these terms is small with high probability for all pairs i and j N.
For the first two terms, note that by Hoeffding's 's inequality (Vershynin 2018 Theorem 2.6.3)
PP (UT p1) -01>>>>>>> <||A|| / Mlo((n/))
ci ||]|
logg/))()/))
eexp
3
9
||
2exp
log log(nz/))
9
c1e2/9
8
2
n
8
30n*
14

---

Published as a conference paper at ICLR 2022
where the last incquality follows since the constant c 2 be chosen be large enough and because å < 1/C for a large enough constant C. Therefore, by taking a union bound over all j E N
Ej 10TT (1) - 4i c||u|| Vlo((n/))
(4)
3
30
Using analogous argument also show that
elaal / Vlo(n//)
5
P
li E.P, I(U u2) gil
<
(5)
3
30
Next, using (Chatterji Long
2021
incquality (15)) we get that
la Oil cv dlog(n/0)
8
P
3i o e [n],
(6)
3
30
Combining inequalities
- we get that for all i P and j E N with probability at least 1 - 6/10
2c|| pelllellVoo((mm/
cvdlog(n/0) S cv dlg(n/8)).
2 23
3
3
where the last inequality follows since by assumption d 2 Cnllul2 and because C' is large enough. This completes the proof of this part.
Proof of Part (6) For any E N, 24 = 12 + Uqe. Recall that μ4 -/2 = 0, thus
| . 2x| 111 (Uq))l-
Invoking inequality 4 proves that this part holds with probability at least 1 - 5/10,
Proof of Part This follows by an analogous argument as in the previous part.
We continue by defining good event that will work under for the rest of the proof.
Definition B.3. the training dataset S satisfies all the conditions specified in Lemma B.2 then we call it good run.
Going forward in this section shall assume that a good run occurs.
The following lemma provides some useful bound on the loss ratio at initialization and guarantees that the loss of example remains in the polynomially-railed part throughout training.
Lemma B.4. Recall that (10) 8w2/31(pp w w/13 (22), and that w; 1 if i P and w, if
i E N. On a good run, for all + [n]
(0)
1/3
W.
Furthermore, if the step-size is sufficiently small then on good run, for all t E {0, 10. and for all E [n]
11)
0(1) - (B
Proof Consider E P then
(6)
31/
2; 200 2/3 (z:
1/3 uz
2/3
+ + 1//w//31111
Vallllllooglae log(n/6)
2
2cww 1/3 (n/6)
<
2/3 2/3
2/3/1/
n1||pu|12
3 31pp||
16t 2/3 2/3 1/1l11111
15

---

Published as a conference paper at ICLR 2022
where (i) follows by Lemma B.2 and (ii) follows since |/ 2 Cn² log(n/6) C+2 log(n/0) 2
22/3 log(n/0) for large enough constant C. Similarly, we also have the lower bound
24 : -000) 2 2s M1 1///822 42)
||a112 - w 10 / (uulllloog///)) 2 2/333/// nn|uul| 2c1w llg(n//)
Sw 2
Recall from the definition the loss that we set B = nw. Now again since I|ul z 2473 2/3 log(n/6), and because we choose 3 new we infer that
8112/1||uu|1
2, ( (3 1)
Since the margin of the point is larger than (3 1) therefore by the definition of the loss function above we have that
1 24 8(0) (3 1)
and hence
S 10)
S 2w2/3n||a|
(7)
16 n |||
By mirroring the logic we can also prove that for all E
1
(8)
16wn ||
By combining equations and we immediately get that
W 1/3
2
This proves the first part of the lemma.
To prove the second part we shall prove that the loss on each example remains smaller than 1/2, which ensures g(9) is equal to the polynomial loss function. Note that
IPI
W|W|
L(o(0))
Σ (0)
())
S 11/2.
(9)
2w2 ||
2wnllp 12
2wnl|a|2
iEP
iEN
This proves that 8 < 1/2 for all E [m]. By (Ji et al. 2020 Lemma 2) we know that the step-
size is small enough then the sequence (ī.((()} is non-increasing. Hence, we have that (t) 1/2 for all E (0, 1.... and for all samples. This wraps up our proof.
The next lemma lower bounds the inner product between the normalized gradient descent iterates, and μr and μ22
Lemma B.5. Let e. and be absolute constants. Then, on a good run, for any E 1,
11 ((++1)
#1 ((0)
|
1
|
|0(+11)|
2cvd
[0
X
on [7
Ei Ei((() - w.tk
Eiep -w,(()) c' ('loognn/o)
E.
Eier ((p
Σ Eie(n) -wi((())
and
11 (00)
|1113 / M 2cvd
111
(1
1000
mn INT Eimo Eretm mu (1)
Eien -wz((1)) d' d' [alll
Eier w((((1)
E' E'=o Eie(n) ((((((
16

---

Published as a conference paper at ICLR 2022
Proof Let us prove the first claim for the inner product with μ1j The second claim regarding μ2 shall follow analogously. For any & E {0, I,... by the definition of the gradient descent step, we have that
P1 ((++1) = =11 .00 + 1 Σ 1ip1 2/ (-2(0)
+ Σ
23 (-c(0)
wipl
REP
EN
Note that by the definition of the loss function have that Parts T and (6) of Lemma B.2 we get that
2 0 for all and all i. Thus by
MI 0(++1)= 2 11-100 000) + a|ll!1?
Σ
wilt - -inllall v Vlo((n/))
- wiek?
2
VEP
NEN
M1 0(()) + 7111a11
wil n|
CiVVloge log(n/8)
1
Σ
wwll
||1||
VE(N)
SEN
c1 ciylog(n/d)
((0) +
wret (())
-weettt ((())
M1
2
LEP
TEN
where is the constant from Lemma
B.2
Unrolling this inequality over steps we have that
f1 00++1)= =1 00(0 + .
C1 (lvlog(n/)
Σ
Σ
wil
Σ
(10)
||
LiEP
ENN
On the other hand, by the triangle inequality we know that
| < |1000| + m/| (((0()))
= =11000 + 1
Σ
22( (i:ue((()))
iE(n]
Σ 24 2 2 (100
S
l1000l + 1
Σ 2 ((())((1)) ((t))
- mww
(II)
REP
iEN
Now note that
Σ 22 (00)
(10) 11 + Σ (2) 23)
REP
EEP
ijjEP
Σ
1 2
100 (110)1 + v dlog(n/8))
(1ell
61
PEP
ijjEP
(0)
- (7())
((0) + IPI(|AB] + /dlog(n/o))
Σ
C1
max-
JEP
iEP
CI
maxx JEP
(11)) )
(d + P|l|u| + |P| (dlog(n/0))
Σ
(())
SEP
2
(18))
d
Σ VEP
e(())
C2
P
where (1) follows by using Part I and Part (3) of Lemma B.2 (it) follows since -e500 is positive
for all j [n)), and (itt) follows since by assumption d > Cn ||| and ||a|| > On² log(n/0) for large enough constant C. Hence we have that
Σ (0()))))) iEP
d
(t)
C2
p
iEP
17

---

Published as a conference paper at ICLR 2022
Similarly, one can also show that
Σ 2
Σ
p100.
-
2
M
IEN
EN
Applying these bounds in inequality
we get that
||00+11|
||0002||
+
d IPI
(1)
W
C2
W
I $100001
+
+
w
d
Σ
-e((t)
W
W
iEP
iEN
d
Σ
((10.
+
V
w
W
#E|D]
Therefore, unrolling this bound over steps we find that
| - 10000 +
d cany
wilfto)
(12)
M
==0
iE
||0001|
V
W
wilftt)
1+
Σ. Eiein) - (ighi11
cally
W
Thus, combined with inequality
I0
we get that,
11 0((+1)
11. -00))
VIN
1
|
10
203Vd
1+
18
X
canyy [NT Di Eielnl
E.=o
Liep wil
ci a (og(n/6)
EiEN
-we ((1))
||l
E. Eie(n) - -wee(()) (())
which completes the proof of the first part of the lemma. The second part follows by an identical argument.
Next, we prove a lemma that shows that throughout training the ratio between the losses between any two samples remains bounded.
Lemma B.6. There is a positive absolute constant 2 1 such that the following holds for all large enough C, and all small enough step-sizes n and for any T I 273. On good run, for all t t (1. and all i + E [n]
(1))
1/3
W
(())
S
c
Proof Let > 1 be the constant from Lemma B.2 above. We shall show that the choice c max (8.2(4c2)1/3) suffices.
We shall prove this via an inductive argument. For the base case, at step O, we know that by Lemma that the ratio between the losses of sample and j is upper bounded by 8 (w//wx))// Now, we shall assume that the inductive hypothesis holds at an arbitrary step t > 0 and prove that it holds step f
Without loss of generality, we shall analyze the ratio between the losses of the samples with indices
i and 2. A similar analysis shall hold for any other pair. Define G. = p(() H, = 6
18

---

Published as a conference paper at ICLR 2022
A, Ht/Gr, Note that,
G411= = ((+++)) (3 10-1) 1)
(00 21 + 1) Ekelni (x(-(x )= 21) (33 - 1)
1
((0) 21 (B - 1) + 11 Ene(m) Wa(Ex 21) 220) 2
e1
1+ m+4) EkE(M) we(2k 21) (((1) 2
1
-G 1 (1() Exe(n) wa(zx 21)
(1())
where (i) follows since- (()) (1( )² as the loss of each example is always in the polynomial tail of the loss by Lemma B.4 Therefore, we have that
He+1 11, 1 - nel0 ExEm wk(Zk 21)
(())
A++1
G4+1 Gt ne( Ene( wh Wx(2 22)
((())
+ ne(") ExE(n) we (Zx 21)
(t)
kk
A
2'
1 ne ExE(n) wx (2* x2)
Now since the step-size 17 is chosen to be small enough, |24 - 2y| I ej d (by Part (??) of Lemma B.2 and by the assumption on d' and because the losses are all smaller than a constant by Lemma B.4 the following approximations hold
1 + 7
Σ kE(m)
wk< 21)
(0(1) kk
2 exp
S
ne
Σ kE(n)
wK(2x + 21) (p(1)) 2
ne
1 + n
wx(2k 22)
(1)
exp
we (zk x2) (efe)
ke[m]
kE(M)
and thus,
A4t1 S A exp
nefo
Σ
wk(2k 21)
((()) 2
7122
(8)
Σ
Wi (2 x2)
(e(1))2
k
(13)
2
kE(n)
kc(m)
Let us further upper bound the RHS as follows
A exp
me(())
Wk wk 21)
(e(0)
ne
Σ
walzk 22) (e(o) (2(0)2
2
kEin]
kE|n]
= A exp
nwi
(1(+))
||21 212
1
nu2
(
1|
2
exp
m)((1)
21)
(1))
2 5
1
Σ
wh(z x2) ((e)))
k
(
((()) 3
(
((()) 3)
A
exp
cindwi
201
el0)
(t)
2
) (Ilul2 v lllo////))
Σ
(229)²
exp
(2))
wk
kE(m)
19

---

Published as a conference paper at ICLR 2022
where (i) follows since for all i [n], d/a I | I ad and for any j # k. 1zg 2kk S
< [Illl2 vdlog(n/5) by Lemma B.2
Continuing get that,
Aete S A exp
Candur
ndwz H
201
canl (G+ (1u11++ + vdlog(n/0))
Σ We (ct)
x exp
kE/m]
[1 _22
A₁ exp
2c1 ndwz
W2
(2()))
x exp
C277 (Ge + Hi) (1al12 + v /dlog(n/o)
Σ Wk
(14)
kE[m]
With this upper bound in place, consider two cases.
Case (A)
); Using inequality 14 we know that
1 nddurGG A7
20fwi
Act1 S A exp
2c1
W/2
C217 C21) + He) (11m132 + vdlog(n/0)
Σ
((())
x exp
wk
AE(m
S A exp (cindw G?) exp c2n (Gi + He) (1ul + vdlog(n/0)
Σ Wk
(2)0)2
(20))
kE(n)
Now the loss on each example is less than the total initial loss 1/2 (see equation
9 and therefore,
A4+1 S A, exp (candw)) exp c4n [1al|3
/dlog(n/ö)
wn
(
Acquii
1/3
exp(1/8) 2
4cfum
1/3
(2)
W1
1/3
U2
U2
W2
1/3
where (i) follows by choosing the step-size 17 to be small enough and because A. this case, and (ii) follows by the choice of constant c > 2(4c))2/3 from above.
in
wa
Case 2 4 ww
< A <
2w ): In this case again by inequality 14
W2
1
2c7wi
A41 S A exp
A3
2c
w22
can (Gr + Hi) (1u|1 + /dlog(n/0)
Σ kEinl
(ef))
exp
wk
1
13 A3- 262
Axp
2c1
w22
e2n (A, + 1) (1l112 dlog((/0))
exp
Wk
G
kE(m)
20

---

Published as a conference paper at ICLR 2022
Continuing we find that,
(1)
1 Indwa2
2
w1
A4t1 S A exp
A
201
W2
1/3
2/3
Co7 max
[1u122 +-++Vlll Vdlog(n/o)
E we
exp
W22
kE(m)
1
2cwwi
A exp
A
201
W2
1/3
(11411 + Vdlog(n/))
Weee
exp
min W1, w2
keIn]
(61)
20fwi
A₁ exp
201 nd A
W2
exp
(oonwiG2 (Iul12
+ vdlog(n/0)
(IP) 11/+1))))))))
1 ndwzzc
20qw1
= As exp
A
2c1
W2
[P] 1 )
exp
G (lul12
+ v dlog(n/8)
(69)
2c/w1
I A exp
2c1 ndwr
A
exp
(2comunCz [Ill v /log(n/0)) n)
w2
(60)
2cfw1 cxp
< A cxp
2c1 ndwrzG
22omurr (lall + vdlog(n/5)) n)
= A, exp
-cpwi G2 (d-orm cn (1u112 + /dlog(n/5)))
where (i) follows by the inductive hypothesis which guarantees that
cl
m1 cw-l33 (Mi)
2 S
follows since wi = if & E P and we = w if E W. Inequality (itt) follows since w < 27 and since (PI S n, and finally (in) follows since in this case A detwi dimension
Now since by assumption the
w2
d 2 2 2 C2 log(n/0)
1/3
for large enough constant C. Hence, we have that Ac+1 S A: S (5((")) 201
in this case.
Recall that since we assumed the inductive hypothesis hold, the two cases analyzed above are exhaustive. This completes our proof.
The next lemma uses the loss ratio bound that we established to show that the difference between the gradient of the losses over the positive cluster and the negative cluster is small any iteration.
Lemma B.7, For any positive ē, there exists a < c < such that, for all large enough C, if the step-size y is sufficiently small and ta 2
S u S 2r3 then on a good run, for any & E (0. 1,...
-w @vlog(n/8) EPP
Σ
- 2 c
|M|||
iEN
1e(n]
and
Σ ((tt δy (//oo(nn/))
((((( (1)
wilti ((1))
wi
||1||
21

---

Published as a conference paper at ICLR 2022
Proof We begin by proving the first part of the lemma. Note that since [n] P UN to prove the first part it suffices to instead show that
EVlog(n/0)
(1 (1-c) c)
will
Wi
2
c+
-
IEP
VEN
ōy (v/oo(n/0)
- (1 c
(1) 2
c+
||
W
pit
iEP
iEN
č iVlog(n/0) |a|||
10) 1002 >
(
-
(1 -
c+
iEP
VEW
(since - -110)
(e )a for the polynomial loss)
τV \Vlog(n/5)
< (1 c) Pl
min
10 c
w|W1 max (2)))
iEP
ēy (lg((/65)
maxie 12)2
- (1 ()- 2
c+
||ا|||
minsep (2 12
ōv 1og(n/8)
+ (1 - C)T (1-c)T 2
c+
||||||
WC1
2/3
(by invoking Lemma B.6 note that C1 2 1)
c)
T = 1/3
c+
2 vC
(since |||||| v Cnn log(n/0), where C is large enough constant).
Since C' is large enough, we now choose the constant 0 < c č/ VC) is at least (2)1/3, This proves the first part of the lemma.
< 1 to be such that (1 - (c)((((((c+
To prove the second part of the lemma, note that again since [ni] PUN suffices to show that
EVlog(n/0) ||
Σ IEN
c+
SEP
= (1 c)l
w min
(20)
c ē log (n/0))
P
max EEP
( (())2
TEN
|||||
(oog(1/8)) |Mll
c +
max (c!0)²2
w >
c)
minjEN (1, (1)))²
i (on((1188)
c
4 w >
2/3 T
(1 c)
C1 c+ vC
6
+= w//3
c)
w 1/3
21/3
where the last implication follows by the choice of e from above. This completes the proof.
We now have all the pieces required to prove our main theorem. Recall its statement.
Theorem 4.2. For any 0 < Ö < 1, there is a constant e such that, for all large enough C and for any < 8 < 1/C, under the assumptions of this subsection the following holds. If the weight
22

---

Published as a conference paper at ICLR 2022
2 S 2T then with probability at least 1- 8, training on produces classifier 01 satisfying:
cn ||
TestError [01] = (ax.)))-Pon sign (0 x
* y/
S exp
d
Proof First, by Part 8 of Lemma
B.2 know that the data is linearly separable. Thus, by
Proposition 4.1 we know that
g( [[0Ce]]
0, lim
||
Given this equivalence, by Lemma B.1
we know that
PP ((c,)))PPex
sign
00
x
* y
g(a)
sign
lim
|
z)
#
-dd
( l1
exp (-o
0l0
41
2 exp
lim (0000
|
lim 10000
(
(15)
000) My ||ero
g pg
We shall now establish lower bounds on limy-+o
and lim
to obtain the desired
||000]
g60
g(9)
bound on the test error. Let us lower bound lim follow by exactly the same logic.
The bound on lim [
shall
|
By Lemma
B.5 we know that
P1 g(++1)
lim
1-000
|
Mi (
1 VIN1
[[(+T)]|
+ lim
201 vd +00
1000
x
OLTV TNT 23
2iclal 10
(og(og/1/0)
Σ
w.l w/((()
C2
||
iEN
@ 11lull2// W
lim
x
201 dd
1000
[0:0
c1dl
[ Li Eec(e) -w, e
C2 (log(//))
will(b)
wi(((s)
||
LiE
EN
||a||2 W
lim
20, Vo
1+
000
/n [NT
d
Eiso E.emm - mm)((())
wi(((() C2 C2 (oolon//))
wi(((()
lim
(16)
||||
LIEP
VEN
where (i) follows since μr (()) is bounded and ||0(++1]| - oo by
Ji et al.
2020 Lemma 2).
We will now show that the first limit in RHS equals To do this, first note that
lim 1000
1
lim
CLTV
1N1
E1
E
nc p(
onT [N1
Σ
E
23

---

Plugging these lower Published as a conference paper at ICLR 2022
Now we will show that
|1000
lim
/ IVT Σ Σien
wil (()0)
10000
2 O, since -ulk? (((
First note that
2
0, so to show that this limit equals
envvdE Exe(al - C(o)
O, it suffices to show that ennvad E. Eiein -w,(/
(() grows unboundedly - Using
inequality (22 from above get that,
||0(++1)| S 10000 + camp
wil
The norm ||0(0)|| finite and we know that ||00|| + oo by Ji et al. 2020 o Eie(m) -w e (s) must grow unboundedly. This proves that
Lemma 2), therefore
lim (-000
1
1
6(0)
annvd Eielnl
as claimed. This combined with inequality (16 yields the bound
E.=
EiEp wilt()
02 (og((1/1)
EiEN wr(((s)
lim M1 00++1) 1050 |
1111
VW
Iall
2
lim 1120
201 vd
Ei= Eie(m) -wil(()
callull VIN1
s== Σie(n) -w;e?
lim (000
Vd
== Eie(n) - -w,e,1) ((10)
callu|1 VWN
Vd
callu|12
VTd
(1) callm112vn
Vrd
where (i) follows by invoking Lemma B.7 and (ii) follows since similar argument also show that lim, mi mi-a(++1)
|P| 2 n/2. As stated above, using
<a <allel /o.
[0(++1]||
Vrd
bounds into inequality (15) completes our proof.
C PROOF OF THEOREM 4.3
In this section we will prove a lower bound on the test error of the maximum margin linear classifier 0MM. Here we will work with the exponential loss
{(x) = exp(
Define the loss Σ(0) - Eie(n) ((nar) 0) = Eiejn) ll 0). For step-size n, and initial iterate
g(0) = (this choice of initial point is for the sake of convenience, it does not affect the implicit bias of gradient descent) for any E {0.1....)
g(++1) g(t) 1) ((
24

---

Published as a conference paper at ICLR 2022
be the iterates of gradient descent. We let e be shorthand for {(2; B and therefore, g ((0) T)((() = g(()) +
2
The results by Souddyy et al. (0188) guarantee that for a small enough step-size the direction of the iterates of gradient descent lim [ OWM Therefore, we will instead prove lower bound on the asymptotic iterates of gradient descent.
g(t)
As we did in the proof of Theorem 4.2, going forward we will assume that good run occurs (see Definition B.3). which guarantees that all of the conditions specified in Lemma B.2 are satisfied by the training dataset S.
With the setup in place, we shall now prove this theorem in stages. Throughout this section the assumptions stated in Section[422 shall remain in force. We begin with lemma that shows that the margin of the maximum margin classifier scales with vd/n.
Lemma C.I. There an absolute constant & such that, on good run, for all large enough C, for all i E [n]]
d
0MM 2 V
Proof We will prove this result by constructing a unit vector e with a margin that scales with v d/n. This immediately implies that the maximum margin classifier must also attain this margin on all of the points.
Define e to be as follows
Φ = Eie
[[jee
We will first bound the norm of the denominator as follows
2j
|
1|
2j
JEIn]
jEIn]
jyk
||
12g Zk
jE(n]
(1)
- and + cn? (Iuu12 + v /llg(n//))
1+ cillall?
d + ny (o/lo(n//)
= and
Vd
2cnnd
(17)
where (i) follows by Lemma B.2 and (ii) follows since d 2 Cnl|ul|2 2 n2 log(n/6) where
recall O is sufficiently large.
Now we lower bound the margin between numerator and 2g for any is E [n]
Σ
|
+
23
2 ||
2
2k
(6)
d
2
(nn(1 v d dlog(n//))
61
d
S5n/log(m///
Vd
d
(18)
2c1
25

---

Published as a conference paper at ICLR 2022
where (i) again follows by invoking Lemma B.2 and by the assumption on d.
Combining inequalities 17 and 18) yields that for any k E
[Mx]
d
cV d
Φ 2/e 2
201 v 2on
This proves the result.
The next lemma provides control over the rate at which the norm of iterates 0(() grows late in training.
Lemma C.2. There is an absolute constant such that, for all large enough C, if the step-size is sufficiently small then on a good run, there exists a to such that for all t to
|10(+111| 2 |100001
V
EE(n]
Proof By the definition of gradient descent
|10(++1) | (10(0) +1
e(2221' 2011
sE(m]
||0(0)|1++ 2m
(1) 24 8(() + Σ
(10) 201
kE|n]
iE|n]
z || + 2n
Σ
((0) 2; B(1)
(19)
kE(n]
Now we know that g(9) that for all i E [n]]
- @MM- Also note that in the previous lemma (Lemma C.1 we showed
d _h n
0MM- 24 2 ci V
Therefore, there exists iteration & such that for all t ti and all i [n]
(
|
Continuing from (9). for any 2 b1
[ 1|2 > ||000) 2n sE/m]
c(9) 23 g()
2 21 + c. 1
(1)
TE
= 11000
+ cany E
EiE(m)
|10(0)
Taking square roots we get that for any t 2 t
d cnny n
ErEW 650
| > |10 IN
1
(20)
|
Further by (Ji et al. 2020 Lemma 2) we know that | - xc, so there exists l2 such that for all t 2 t2, ||0(t) || 2 ennvnd nd
Thus, for t 2 t2 we have
Liein) (1)
d 50s) <8 ciTy
<8
(21)
n
EE|m
26

---

Published as a conference paper at ICLR 2022
where the last inequality follows since the initial loss is equal n, as ((0) and the total loss is decreasing again by (Ji et al. 2020 Lemma 2) if the step-size is small enough. It is easy to check that for any 0 S x
I 4
VI+ 2 1+
Thus, combining inequalities 20 and (1
we get that for 2 l0 max (11x(11,12)
1+ cnyy Eielnl e
2 ||000)| 1+ cnny n Σie(n 800
|
2
1
|
4|10(*)
d + TV
Σ
n iE[n]
which completes our proof.
Continuing we will show that throughout training the ratio of the losses between the different exam- ples are bounded by constant. This ensures that each example roughly "influences" the gradient update by the same amount in each step. However, since the number of points from the positive cluster is larger, the gradient update shall overall be more highly correlated with the mean of the majority positive center (ii than the mean of the minority negative center 1/2-
The proof identical to the proof Lemma 11 by Chatterji & Long (00T)) However, since our setting is slightly different to the setting studied in that paper we reprove the result here.
Lemma C.3. There is an absolute constant such that, for all large enough C, and all small enough step sizes on good run, for all iterations I. E {0, 1, 1,...} and all i,j E [n]
p(
0 S c.
Proof First note that L(((0)) Eela] 4
= and since step-size 1) is small enough training loss
is non-increasing by (Ji et al. 2020 Lemma 2).
Let C1 be the constant e 2 from Lemma B.2 We will show that e = 4e suffices.
We shall prove this via an inductive argument. For the base case, at step = 0, we know that g(o) = 0, therefore the loss on all of the samples is equal to 1. Now, we shall assume that the inductive hypothesis holds an arbitrary step t and prove that it holds at step + +.
Without loss of generality, we shall analyze the ratio between the losses of the samples with indices
i 1 and 2. A similar analysis shall hold for any other pair. Define G. e(0, H, 6
A, = H. G.. The ratio between these losses at step & + 1 is
A exp( (0+(1) 22)
cxp( 0(++1) . 21)
exp( (s((-( 7) ExE(n) (())2x) 22)
exp(-(A1)) # Eve(nl (()) (()) 2xx) .21)
A₁ - eex
-7 Σ
( (2k 22 - 2x 21)
kE(n]
(1) || 1|2 11011121 122
(t)
A, exp
7]
Zh 22 +
2g 21
k#
-xp
exp
-1) He|la2 Gellza
(+)
Z4
22
2
1ish
z 21 ))
A, exp
-1)
H 22 2
Gellz1
k
221
Σ
((0)
k
k
27

---

Published as a conference paper at ICLR 2022
Now note that by Lemma B.2 for all + J E [n], d/a I ||ll| I c and (Illl vdlog(n/o) and therefore,
12, Eg² s
A--1 S exp
-1
Híd
-Gild- - 20 (1u112 + Vdlog(n/))
Σ
ke(ml
Gid
A4 : exp
-1
(Ar - -c]) -201 (11l|12 + vdlog(n/0) G. Σ
C1
G.
kE(n)
(#)
Ged
& A exp
11
(Ai -c²)- - 8c8 [|||] + /dlog(n/8) Gin)
C1
G
|111/2
ny nvlog(n/0)
A, exp
A - G 8c7
+
C1
Vd
(81)
A ot - sct ( +t²)))
A exp
C1
(i1) [nGGdd
A cxp
(A, 20t)
(22)
C1
where (i) follows since by the inductive hypothesis / S c 4e (it) follows since by
assumption d 2 Cn|lua| 2 C log(n/6), and (fit) follows since is sufficiently large.
Now consider two cases.
Case (A, $ 2c?): By inequality
(22
A441 S exp (oxpp-10 (-rGrd (Ar 20t) = Axexp
(nGrd (2c² - A.)
< 2e exp (2nc G.d)
< 2c exp (2me1nd)
4ef,
where the last inequality follows if the step-size is sufficiently small. Case (2o7= S A S 4c7 c): Again by inequality (22
(-rGed (Al-
A411 S A . exp
SA s 4c7.
C1
Thus, we have shown that Art1 4c} cin both cases. Since we assumed the induction hypothesis to hold at step f, these two cases are exhaustive, and hence the induction is complete.
The next lemma proves an upper bound on the difference between the inner product between ((++1). #22 and the corresponding inner product iteration Since start at ((0), unrolling this over t steps gives upper bound on inner product ((t) U2 for any > 0.
Lemma C.4. There is an absolute constant such that, for all large enough C, if the step-size is sufficiently small then on a good run, fon,for all E {0, 10...
(glct1)- - 0(0) ((112) cnllM112 Σ (1)
se(n]
28

---

Published as a conference paper at ICLR 2022
Proof By the definition of gradient descent step
(0(++)) 0(0) (- =
Σ
c 2s
(-H2)
x
[n)
(6) 3r |all
(()) + eenlll log(n//0
2
IEN
EEP
(6)
3n 30|1u|11
ca/M
C2 c2|P1 Pl
+ ccmlllll Vlg((/0))
2
n
n
iE mm]
[m]
302n|1u|1
|P]
Vlog(n/0)
Σ iE/m]
2
n
(P]
[W]
log(n/5)
- /e1nlluu| max
|P]
|p|||
where (1) follows by Lemma B.2 and (wi) follows by the loss ratio bound Lemma
C.3 Since by
assumption || 2 Cn2 (n infer that
v /log(n/0)
W
|||||
n
PP
Thus,
W
/log(n/0)
|7|1 T
(a(++1) (-w2) s 302nl
wul? max
[P]
||||||
[m]
ic(m)
wrapping up our proof.
With these lemmas in place we are now ready prove our result. Let us restate here.
Theorem 4.3. Let N(O, Iaxa)- There exist constants and d' such that, for all large enough C' and for any 0 < < 1/C, under the assumptions of this subsection the following holds. With probubility at least 8, training on S produces maximum margin classifier 0PM satisfying:
TestError [Ohm)] = (Z..g)~P.. [sigu (Thams
C
+
Vd
where t is the Gaussian edf. Furthermore, if the imbalance ratio 2 d y ||ll? Vd
then with probabil-
ity at least - 5, (estError(0mm.) 2 8-
Proof The test error for θMM is
TestError (0MM)]
P (a..))~Pus
sign
@OmM 2) + *v/
sign (Phm (my + +q)) +1
1
sign (Tha (u2 o)) + 4-1
2
> PP (ox.
sign (Omm (I12 + 1) -1]
2
Onmm u12 - 0mM < 0]
2
T
PMM 9 -0MM (-H22
p~N(0.
P Pc~N(0.11
[5
<<< -0MM- (-r22)
(since -Jum 9 N(O, 1))
2
( 40m
(-p2))
(23)
2
29

---

Published as a conference paper at ICLR 2022
where & is the Gaussian cumulative distribution function.
With this inequality in place, we want to prove an upper bound on (0mm (-wz) Now, since
0MM. suffices to prove an upper bound on (lim 000) (1)((-2)) 2
instead.
|
To do this, going forward let us assume that good run (see Definition B.3 occurs. Lemma B.2 guarantees that this happens with probability at least 1 - 6.
Let to be the constant from Lemma
C.2
then by Lemma C.4 we have that for any t to
g(0) (-Hu2 =((0) (-12) +
(p(+) - g(e-1)) (-p2) +
(olo) - 0(6-11) (-122
8=
S अ aallall
1-1
(24)
where we define 3 = 0(0) (-p2) + Σ (0(.) - (( (-H2).
On the other hand, by repeatedly applying Lemma C.2
we get that
|| > ||0(to]|| + 1
(25)
ic(n)
Furthermore, since ||000|| + 0o (by Ji et al. 2020 Lemma and
|0((+D)
(00)
(0) 24
|=:||
s=0 [E(n)
s=0 iE|n]
< cand
(by Part 1 of Lemma B.2
s=0 EE(n]
cand
+ cari
(8)
0 iE(n)
smio EE
we can conclude that E.=O
E Lignn m]
(()) co.
Thus combining inequalities 24 and (2 we get that
cin Illl
Et Eieln (1)
((t)
(--22)
C1 n1
lim
lim
V d |al
[000]]
||
|| + c29l/ - Eie(n) c(0)
7
Plugging this upper bound into inequality
23
completes the proof.
D EARLY-STOPPING BEFORE MODELS INTERPOLATE
Prior works (Sagawa et al. 2019 Byrd Lipton 2019 found that adding regularization such as strong 1.2 regularization and early stopping can partially restore the effects of importance weights at the cost of not interpolating the training set. such, we compare the performance of our polynomially-taile loss against cross-entropy when models carly-stopped, using the same set- tings as before. For each run here, we select the model checkpoint with the best weighted validation accuracy and evaluate the checkpoint the test set. Figure 5 compares the test accuracies of the etrly-stopped models (IW-ES (w), IW-ES (w") against reweighted models trained past interpolation (IW (w)).
Consistent with prior works, we see that early stopping as a form of regularization improves the test accuracies of both loss functions when used with importance weights. Our polynomially-taiee -talled loss
30

---

Published as a conference paper at ICLR 2022
Parly-stopped
Iubellanced Binary CIPARIO
Subeamplood CelebA
0.70
0.90
Prigetuleed Toos
0.65
Cruss Entrapy
Test Accuray
Trst Accurncy
0.60
0.55
0.80
0.50
0.75
0.45
0.40
0.70
IW (1F)
IW-ES (1)
IW-FS (W/72)
IW (12)
IW-ES (0))
IW-ES (3))
Figure 5: Polynomially-tailed loss versus cross-entropy loss on label shift dataset and subpop- ulation shift dataset for neural networks early-stopped according to the best weighted validation accuracy. * and ** indicate p < 0.05 and p 0.005 statistical significance, respectively. While early stopping is effective for both losses, our polynomially-tailed loss performs even better on im- balanced binary CIFARIO.
gives accuracies that are better than or similar cross-entropy in all weighted loss scenarios. The gain over cross-entropy is statistically significant in the binary CIFAR1O 10 runs. On subsampled CelebA, the polynomially-tan tailed loss with squared weights attains the highest mean test accuracy out of all settings.
E EXPERIMENTAL DETAILS
E.1 HYPERPARAMETERS
E.1.1 FOR SECTION 5.1
Imbalanced binary CIFAR10 experiments. We use the same convolutional neural network ar- chitecture with random initialization as (Byrd & Lipton 2019). We train for 400 epochs with SGD with a batch size of 64. We chose hyperparameters that resulted in stable training for each setting- We use a constant 0.001 learning rate with 0.9 momentum for "No IW". "IW (w)"" and "IW-ES (w)" We use constant 0.008 learning rate with no momentum for "TW (w"/2y", and "IW-ES (1"".."
Subsampled CelebA experiments. We use a ResNe150 architecture with ImageNet initialization done (Sagawa al. 2019). Due to the large dataset size, we use only 2% of the full training dataset as mentioned in the main text. Reducing the computation requirements allows us to perform statistical evaluations of the results over sufficiently many seeds. We train for 100 epochs with SGD with batch size of 64. We chose hyperparameters that resulted in stable training for each setting. We use constant 0.0004 learning rate with 0.9 momentum for all settings.
1.1 FOR SECTION 5.2
To fairly evaluate every method, we grid search the hyperparamters for each method extensively. We kept the same architectural setup before, but adjust the optimization settings such that the models train until they interpolate the training data.
Imbalanced binary CIFAR10 experiments.
Cross entropy Class Undersampling: We use the same hyperparameters as Cross entropy the full dataset and average results over random undersamplings plus initializations
LDAM: Following the original paper Cao al. (201)), we grid search the margin hyper- parameter over [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]. We found 1.0 to be the best.
CDT Loss, LA Loss, VS Loss: Following Kini et al. (2021). we tune т and y with 0 being CDT loss and ? [0.0, 0.5, 1.0, 1.5, 2.0, 3.0 [0.0, 0.1, 0.2, 0.3, 0.4, 0.5). We found т = to be the best for LA loss, 7 0.5 to be the best for CDT loss, and 3, 7 0.3 to be the best
being LA Loss. We grid search across (T.Y)
31

---

Published as a conference paper at ICLR 2022
for VS Loss. Unlike the original paper (Kini al. 2021). found that the best hyperpa- rameters of VS loss are similar to those of LA Loss. We initially followed the recommen-
dations of Kini et al. (2021) and grid searched over (T, E [0.5, 0.75, 1.0, 1.25, 1.5) x [0.05, 0.1, 0.15, 0.2|, but it gave VS loss poor performance (mean test acc was only 58.6% using the best hyperparameters 5 1 0.05). Hence, we did more extensive tuning afterwards.
Poly-tailed Loss: We grid search over (a,c) E [0.25. 0.5, 1.0, 2.0, x [1.0, 1.5, 2.5, We found and exponent e be the best.
Subsampled CelebA.
Cross entropy Group Undersampling: We use the same hyperparameters as Cross entropy on the full dataset and average results over random undersamplings plus initializations.
VS Loss: We follow the tuning procedure Kini 202 for group-sensitive VS Loss and grid search over 7 E [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]. We found = 0.4 to be the best.
Poly Loss: We grid search over (a, [1, [1.0, 1.5, 2.0, 3.0). We found and exponent e = 2.5 to be the best.
Cross entropy + DRO: We tune the adversarial step size
"]g
over
[0.0025, 0.005, 0.01, 0.02, 0.03, 0.04, 0.05, 0.1). We found ny 0.05 to be the best.
VS Loss DRO: We used the best y from VS Loss alone and 7n 0.05 for DRO.
Poly Loss DRO: We used the best from Poly Loss alone and 7lg 0.05 for DRO.
E.2 IMPORTANCE WEIGHT COMPUTATION.
Here we explain in greater detail how we compute the importance weights. Note that the scale the importance weights is important in ensuring stable training. Let there be G groups of subpopulations in the training and testing set. G = 2 for binary CIFARIO and G 4 for CelebA. Let 71 7I...., RG be the counts of each group in the training set. Let be the total number of training examples. In our case, the test set is balanced across the groups. Our procedure for computing weights is:
1. For each example that belongs to group g, compute the unbiased weight: w; 1/ng-
2. Exponentiate the weights by if necessary: w; + W. No importance weighting corre- sponds to c = 0. Unbiased importance weighting corresponds to
3. To adjust for the scale of weights, normalize by the average exponentiated weight across the fill training set: w; +- w:/ ) Wi. Only normalizing across each minibatch can result in unstable training, especially when a minibatch contains no representatives from group.
E.3 EARLY-STOPPING METRIC.
We use the checkpoint with the highest importance weighted validation accuracy when early stop- ping. We compute separate importance weights of the validation set with respect to the test set, and reweight the validation accuracy using unbiased weights, even when the training weights are biased. Our procedure allows for the situation where the validation set is not exactly the same distribution the training set.
32

---

Published as a conference paper at ICLR 2022
E.4 EXACT NUMERICAL RESULTS OF OUR EXPERIMENTS
Cross Entropy mean
Poly-tailed Loss mean std. err.
std. err.
p-value
Dataset
Setting
Subsampled CelebA
Etrly-stopped
IW
79.3%
0.4%
80.7%
0.6%
0.014
IW-ES 84.9%
0.7%
84.0%
0.9%
0.762
IW-Exp-EI
85.1%
0.7%
85.9%
0.8%
0.202
Interpolating
IW
79.3%
0.4%
80.7%
0.6%
0.014
IW-Exp
78.7%
0.4%
82.7%
0.4%
0.000
No IW
79.6%
0.4%
78.5%
0.4%
0.999
Binary CIFARIO
Etrly-stopped
IW
57.8%
0.4%
60.4%
0.3%
0.000
IW-ES
62.5%
0.7%
63.4%
0.5%
0.022
IW-EX Ex--EX
61.2%
0.8%
63.5%
0.6%
0.001
Interpolating
IW
57.8%
0.4%
60.4%
0.3%
0.000
IW-Exp 57.4%
0.6%
63.0%
0.6%
0.000
No IW
60.5%
0.8%
56.4%
0.4%
1.000
Table I: Numerical results corresponding to Figure 3 and 5
Here "Exp" corresponds to exponenti-
ated weights. We use 3/2 and as the exponents in Binary CIFARIO and CelebA respectively, We use = 1 for all of these experiments without tuning a.
Setting
Summary of method
Best settings
Mean test ace
Std
err
Cross Entropy
N/A
60.5%
0.8%
Cross Entropy IW
Classical importance weight- ing
N/A
57.8%
0.4%
Cross Entropy Class
Balance the classes by throw- ing away majority data
N/A
58.5%
1.4%
undersampling
LDAM
Add class dependent
largest margin=1.0
58.7%
1.6%
stants to logits
CDT
Multiply class dependent con- stants by logits
0.5
60.2%
1.6%
LA Loss
Add class dependent con- stants to logits
66.9%
2.1%
VS Loss (best setting around range suggested by paper)
Multiply by and add class de- pendent constants logits
T = 1, 0.05
58.6%
1.4%
VS Loss (our own tun- ing)
Multiply by and add class de- pendent constants to logits
3, 0.3
69.3%
0.9%
Poly-tailed Loss
Change loss function and exponentiate importance weights
- 2, 3
67.3%
0.8%
Table 2: Results imbalanced binary CIFAR10, corresponding Figure (left).
33

---

Published as a conference paper at ICLR 2022
Setting
Method summary
Best tings
set-
Mean test acc
Std err
Worst group test
Std
err
Cross Entropy
N/A
79.6%
1.2%
43.1%
2.9%
Cross Entropy + Group undersampling
Balance the groups by throwing away overrep-
N/A 82.3%
3.2%
72.1 %
8.6%
resented data
Cross Entropy IW
Classical weighting
importance N/A
79.3%
0.4%
43.1%
2.9%
VS Loss
Multiply by and add 7 = 0.4 class dependent stants to logits
82.6 %
0.7%
51.3%
1.5%
Poly-tailed Loss
Change loss function and exponentiate impor- tance weights
a 2.5
2,
82.4%
0.8%
53.3%
1.5%
Cross Entropy DRO
N/A
84.8%
0.9%
60.4%
2.4%
VS Loss + DRO
Change loss function and use DRO
7 0.4
83.2%
0.9%
58.2%
2.0%
Poly-tailed Loss + DRO
Change loss function and use DRO
2
86.7 %
1.1%
66.5%
1.9%
Table 3: Results on subsampled CelebA, corresponding to Figure (right)
34


Reviews:
[{"review_id": "rKZXby1L_r", "reviewer": "Reviewer_s5yg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strengths]\n- Clear presentation. Figure 1 gives an intuitive example illustrating why importance weighting could fail on exponentially-tailed losses.\n- The proposed polynomially-tailed loss could be a very practical tool for importance weighting.\n- Theoretical results look solid and well justify the polynomially-tailed loss.\n\n[Weaknesses]\n- The theoretical results are based on the assumption of sub-Gaussian data which could be unrealistic.  \n- The polynomiallhy-tailed loss does not seem to admit a probabilistic interpretation as the distance between two distributions. How would it perform on a softmax layer?\n- The proposed loss has a parameter alpha. However, the impact of the parameter is not discussed in either the theoretical or empirical section. Does the choice of alpha significantly affect the result? \n\n", "summary_of_the_paper": "In this paper, the author investigates whether importance weighting is incompatible with the training of overparameterized neural networks. In contrast to the recent observation that  importance weighting is ineffective in current deep learning paradigm (Byrd & Lipton 2019), the authors show that it could actually be helpful using polynomially-tailed losses. Both theoretical justifications and empirical evidences are provided to support the claim.", "summary_of_the_review": "Overall, I think the paper provides answers to an important question. Both theoretical and empirical results are provided to corroborate the claim.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Vsir-xRW3Kj", "reviewer": "Reviewer_DWSu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "#### Strengths\n\n1. This paper points out a potential way to make training overparameterized neural nets compatible with importance sampling, which is to change the loss from cross-entropy to a polynomially-tailed loss.\n2. A full characterization for the implicit bias of GD on polynomially-tailed loss is given by (2) in Section 4.1 (although it is an easy corollary of Ji et al. 2020). It is clear from (2) that the implicit bias changes with the importance weights.\n3. The separation between polynomially-tailed loss and exponentially-tailed loss in Section 4.2 is simple and interesting.\n\n#### Weaknesses\n\n1. The theoretical analysis is only for linear classification. As for the generalization aspect, the analysis is even more restricted as it only holds for the dataset with two sub-Gaussian clusters. So the theoretical result is not very strong. Although we can certainly draw some insights from this simple setting, it is still unclear what generalization guarantees polynomially-tailed loss has in general.\n2. The paper claims that the implicit bias of GD changes with importance weights, but such change could be minor when the degree of the polynomial is high, i.e., $\\alpha$ is large. In the equation (2) in Section 4.2, if $\\alpha \\to \\infty$, then $\\hat{\\theta}_{\\alpha}$ is just the max-margin solution. Thus the choice of $\\alpha$ cannot be arbitrary, and a polynomially-tailed loss with a high degree can perform as badly as the exponential loss. In the later sections, the authors always use $\\alpha = 1$. It would be nice if the authors can carefully discuss more the choice of $\\alpha$ and provide a recommendation for the choice of $\\alpha$. If $\\alpha = 1$ is the best in the theoretical setting in Section 4.2 and in the experiments, then the paper should highlight linearly-tailed loss rather than polynomially-tailed loss.\n3. The experiment results are not compared against many baselines. It is unclear whether the 2%-3% test accuracy difference can be considered to be a big gain, and whether other methods (e.g., undersampling) can obtain the same gain in terms of the test accuracy. Although this paper is mainly a theoretical paper, the authors do claim that polynomially-tailed loss has practical value, and the current experiment results are not strong enough to support this claim.\n\n#### Minor Comments\n\n* Page 20 looks wried.\n* The current proof for Theorem 4.3 is trajectory-based, i.e., it analyzes the trajectory. However, Soudry et al. (2018) have already proved that the convergent classifier is the max-margin classifier, and one can easily show that the max-margin classifier is unique. So I'm wondering whether Theorem 4.3 can be proved by just analyzing the properties of the max-margin classifier, without analyzing the trajectory. It is not a weakness of this paper, but if this paper can provide an argument directly for the max-margin classifier, then the readers will better understand why the max-margin classifier is bad in this setting. After skimming the proof, I think it might be possible to translate Lemma C.3 into a lemma on the upper bounds for the ratio between dual variables (instead of loss values), and it sounds promising to use this upper bound to bound the influence of the samples from the minority class, and hence the max-margin classifier generalizes poorly.\n* Section 4.1 should clarify that the optimal solution for (2) is unique. Although it is proved in the appendix that the solution is unique, but clarifying this in the main body can avoid confusion.", "summary_of_the_paper": "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.\n\n* 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.\n* Experiments on Imbalanced Binary CIFAR10 and CelebA show that the polynomially-tailed loss performs better on imbalanced datasets.", "summary_of_the_review": "This paper provides interesting theoretical results for using polynomially-tailed loss to resolve the incompatibility between importance sampling and training overparameterized neural nets. However, the theoretical setting is quite restrictive. I think this paper is on the borderline, but it is ok to accept this paper.\n\n------------------\nPost-rebuttal update:\n\nI am glad to see that the authors have conducted more experiments to compare their method with baselines. I'm not an expert in the empirical methods for dealing with distribution shift, but I think the current empirical results they have are great additions to their theoretical analysis. I have increased my score for the empirical novelty and significance accordingly.\nAs for the theoretical analysis, which is the main selling point of this paper, I still believe the current setting is restrictive, although I know some previous works are studying it. Therefore, I would like to continue to vote for weak acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KsW1C6lYwr", "reviewer": "Reviewer_AUFR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is well-written and enjoyable to read\n- The theoretical claims are sound and well presented\n- Theorem 4.2 is interesting: It extends the analysis by Chatterji & Long to imbalanced setting and the finding about the scaling of the weight being cubic in \\tau is interesting.\n\nWeaknesses:\n- The study is limited to binary classification. It is not clear how to extend the loss to multiclass. At least when it comes to experimental results, multiclass experiments would make a stronger case. \n- Experimental results are limited to a comparison between weighted cross entropy and the new loss. How does the new loss compare to other const-sensitive techniques, e.g. LDAM loss [1], Logit-adjusted loss [2], VS loss [3], DRO (Sagawa et al.)?\n- More generally, while the presentation is from the viewpoint of distribution shift, all study cases (both theoretical and experimental) are with respect to imbalanced data problems. In this setting there has been a lot of recent work, which appears closely related but is not discussed (eg. [1-4]). Specifically, [3] appears to be very closely related (for example, see their Theorem 1; how does your program in (2) compare to the cost-sensitive svm?). I suggest that the authors try to better place their work within this literature.\n\n[1] Cao, Kaidi, et al. \"Learning imbalanced datasets with label-distribution-aware margin loss.\" arXiv preprint arXiv:1906.07413 (2019).\n[2] Menon, Aditya Krishna, et al. \"Long-tail learning via logit adjustment.\" arXiv preprint arXiv:2007.07314 (2020).\n[3] Kini, Ganesh Ramachandra, et al. \"Label-Imbalanced and Group-Sensitive Classification under Overparameterization.\" arXiv preprint arXiv:2103.01550 (2021).\n[4] Kang, Bingyi, et al. \"Decoupling representation and classifier for long-tailed recognition.\" arXiv preprint arXiv:1910.09217 (2019).", "summary_of_the_paper": "The paper shows both theoretically and experimentally that importance weighting is not incompatible  with the training of overparameterized models provided that the training loss is appropriately modified so that it does not have an exponential tail. Specifically, for binary classification the authors propose a new loss function with polynomial tail decay. Theoretically, the new loss is shown to outperform weighted cross entropy for linear models and an imbalanced mixtures of gaussian model. Empirically, the new loss outperforms weighted cross entropy on imbalanced CIFAR 10 and the CelebA dataset. ", "summary_of_the_review": "While I appreciate the author's clarity of presentingtheir ideas/theories/proofs/experiments and the paper's finding is quite interesting, it is perhaps not so surprising especially given the recent works and findings on mitigating the effect of weighted CE failure for imbalanced data. Also, the implications of the finding are not made clear. How does the proposed loss compare to state-of-the-art loss adjustments? Does it apply to multiclass settings? \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "18izF6aYe9r", "reviewer": "Reviewer_46YL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies the impact of importance-weighting in interpolating classifiers. The authors showed that in contrast to the prior works that showed importance-weighting is ineffective due to implicit bias of converging to max-margin, switching to poly-tailed loss circumvents this issue, both theoretically and empirically.\n\nPros:\nOverall, this paper is very well-written and the theoretical results are sound. I really like the idea of using a poly-tailed loss - it is simple, effective, and practical - but by far not an obvious one. This idea circumvents the previous negative results in an elegant manner. \n\nI also like the analysis of poly-tailed loss under Gaussian mixture setting: there are some surprising takeaways, e..g. inverse-frequency weighting being sub-optimal and the optimal re-weighting being roughly cubic in class imbalance. I have never seen these types of results in the prior works.\n\nCons:\n\nThere are some obvious limitations, for example, the gap between linear classifiers and neural networks used in practice, which is a minor issue due to the intractability of analysis. \n\nThere are some more interesting possible extensions, though: for example, a theoretical analysis of (and comparing against) early stopping would be nice.\n\nThere is limited discussion about how to pick the hyperparameter alpha, which can be useful for practitioners.\n\nThe performance boost (2%-3%) is relatively minor. I am not sure about how it compares to stronger baselines.", "summary_of_the_paper": "This paper studies the impact of importance-weighting in interpolating classifiers. The authors showed that in contrast to the prior works that showed importance-weighting is ineffective due to implicit bias of converging to max-margin, switching to poly-tailed loss circumvents this issue, both theoretically and empirically.", "summary_of_the_review": "I like the paper due to its simplicity, effectiveness, and interesting take-aways from theory. There is some room for improvement in the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper revisits importance sampling as an approach for combating distribution shift when training over-parameterized neural networks. Contrary to recent results that suggest that importance sampling is perhaps incompatible with over-parameterization, the authors find that the exponential tail of losses such as the logistic loss is the root cause. For polynomial tailed losses, authors analyze gradient descent on importance weighted polynomially-tailed losses and demonstrate the advantage of importance sampling in a label shift setting.

There paper is well-written and the results are sound. Overall, a good paper.
Decision: Accept (Poster)