# Is Importance Weighting Incompatible
with Interpolating Classifiers?

Ke Alexander Wang111Equal contribution.∗
Stanford University
<EMAIL_ADDRESS>
Niladri S. Chatterji∗
Stanford University
<EMAIL_ADDRESS>
Saminul Haque
Stanford University
<EMAIL_ADDRESS>
Tatsunori Hashimoto
Stanford University
<EMAIL_ADDRESS>
###### 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. _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.

##  1 Introduction

Machine learning models are often evaluated on test data which differs from
the data that they were trained on. A classic statistical technique to combat
such distribution shift is to _importance weight_ the loss function during
training [Shi00]. This procedure upweights points in the training data that
are more likely to appear in the test data and downweights ones that are less
likely. The reweighted training loss is an unbiased estimator of the test loss
and can be minimized by standard algorithms, resulting in a simple and general
procedure to address distribution shift.

Figure 1: 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 even with reweighting. (Right) Our polynomially-
tailed loss restores the effects of importance weights, correctly adjusting
for the distribution shift.

Surprisingly, recent papers [BL19, XYR20] have found that importance weighting
is ineffective in the current deep learning paradigm, where overparameterized
models interpolate the training data or have vanishingly small train loss. In
particular, [BL19] 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. [XYR20] followed up
and provided a theoretical justification for this observation in
overparameterized linear and non-linear models.

To build intuition about why importance weighting fails, consider linear
classifiers as an example. Given linearly separable data
$(x_{1},y_{1}),\ldots,(x_{n},y_{n})\in\mathbb{R}^{d}\times\\{-1,1\\}$,
[Sou+18] showed that if gradient descent is applied to minimize an
exponentially-tailed classification loss
$(\sum_{i\in[n]}\ell_{\mathsf{exp}}(y_{i}x_{i}))$ then the iterates converge
in direction to the maximum margin classifier
$\widehat{\theta}_{\mathsf{MM}}:=\operatorname*{arg\,min}_{\lVert\theta\rVert=1}\left\\{\gamma\;:\;y_{i}x_{i}\cdot\theta\geq\gamma,\text{
for all }i\in[n]\right\\}$. [XYR20] showed that in this same setting,
minimizing the importance weighted loss
$(\sum_{i\in[n]}w_{i}\ell_{\mathsf{exp}}(y_{i}x_{i}))$ with gradient descent
also results in convergence to the maximum margin classifier, regardless of
the weights. To see why, consider the special case where the weights
$(w_{1},\ldots,w_{n})$ are positive integers. This reweighting is equivalent
to simply repeating each datapoint $w_{i}$ times, and the maximum margin
classifier over this “new dataset” remains unchanged. Thus, invoking the
original result by [Sou+18] proves that the importance weights has no effect
in correcting the distribution shift. This result can be seen in Figure 1
where we demonstrate this phenomenon in a simple toy problem.

Such evidence has led some to wonder if importance weighting is fundamentally
incompatible with overparameterized interpolating models. In this paper, we
show that this is not the case. We find that the culprit behind the
ineffectiveness of importance weighting is the _exponential tail_ of popular
losses such as the cross-entropy or the logistic. We propose altering the
structure of the loss to have fatter, polynomially decaying tails instead. We
theoretically and empirically demonstrate that importance weights do correct
for distribution shift under such losses even for overparameterized
classifiers.

Our first contribution is to characterize the limiting direction of the
iterates of gradient descent (its implicit bias) when minimizing reweighted
polynomially-tailed losses with linear classifiers. We show that this limiting
direction is a function of both the datapoints as well as the importance
weights, unlike the maximum margin classifier that only depends on the data
(see the right half of Figure 1). Next, we analyze the generalization behavior
of this classifier in a label shift setting. We prove that when the weights
are an exponentiation of the unbiased importance weights, the test error
decays to zero in the large sample limit, regardless of the level of imbalance
in the data. In contrast, we prove that the test error of the maximum margin
classifier in this same setting must be _at least_ $1/8$.

Finally, we demonstrate the practical benefits of our framework by applying
this approach to experiments with neural networks. In both a label shift
dataset (imbalanced binary CIFAR10), and a subpopulation shift dataset with
spurious correlations (CelebA [Sag+19]), 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 perform comparably to, or better than, state-of-
the-art methods distribution shift [Cao+19, Ye+20, Men+20, Kin+21]222Code is
available at https://github.com/KeAWang/importance-weighting-interpolating-
classifiers.

##  2 Related Work

Early work [Shi00, WYG14] already warned against the potential ineffectiveness
of importance weights on interpolating overparameterized models. [Shi00]
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. [WYG14] showed that when there is a zero-loss
minimizer of an unweighted convex loss minimization problem, then it is also a
minimizer of the (adversarially) reweighted loss as well. Recent work [BL19,
XYR20] has shown that importance weighting fails to have an effect on neural
networks trained with gradient descent, though always in the setting of
exponentially-tailed losses. [Sag+19] 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 [BL19].

A recent line of work [Cao+19, Ye+20, Men+20, Kin+21] has introduced
modifications to the logistic and cross-entropy losses to correct for
distribution shift. [Cao+19] and [Men+20] proposed using additive corrections
to the logits. However, without regularization or early-stopping these
corrections are ineffective since the additive corrections to the logits is
analogous to importance weighting exponential-tailed losses. Multiplicative
logit corrections [Ye+20], possibly combined with additive corrections
[Kin+21], have also been proposed which do affect the implicit bias of the
learnt classifier. However, these do not correspond to importance weighting
algorithms, and further these works do not provide guidance regarding how one
should select these multiplicative corrections in practice.

Our work also connects to literature that has studied the implicit bias of
gradient descent [Sou+18, JT19, Nac+19]. Especially relevant is the work by
[Ji+20] who relate the implicit bias of gradient descent with exponentially
and polynomially-tailed losses for linear classifiers to a solution of a
regularized loss minimization problem.

Finally, our generalization analysis draws from the growing literature focused
on finite sample bounds on the test error of the maximum margin classifier in
the overparameterized regime [CL21, Mut+21, WT21, CGB21].

##  3 Setting

We consider a distribution shift setting where the training samples
$\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}\in\mathbb{R}^{d}\times\\{-1,1\\}$
are drawn i.i.d. from $\mathsf{P}_{\mathsf{train}}$, and the test samples are
drawn from a different distribution $\mathsf{P}_{\mathsf{test}}$ that is
absolutely continuous with respect to $\mathsf{P}_{\mathsf{train}}$. Let
$f_{\theta}$ denote a classifier parameterized by $\theta$. Given a feature
$x$, a classifier maps this feature to $f_{\theta}(x)\in\mathbb{R}$. In this
paper we shall consider cases where the classifier is either linear (for our
theory) or a neural network (for our experiments).

Our goal is to find a classifier $f_{\theta}$ that minimizes the $0$-$1$ loss
with respect to the test distribution:

$\displaystyle\mathsf{TestError}[f_{\theta}]=\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}(f_{\theta}(x))\neq
y\right].$

To handle the mismatch between $\mathsf{P}_{\mathsf{train}}$ and
$\mathsf{P}_{\mathsf{test}}$, we shall study importance weighting algorithms.
Given a datapoint $(x,y)\in\mathbb{R}^{d}\times\\{-1,1\\}$, the classical
_unbiased importance weight_ at this datapoint is given by the ratio of
densities between the test and the train distributions
$\frac{\mathsf{P}_{\mathsf{test}}(x,y)}{\mathsf{P}_{\mathsf{train}}(x,y)}$.
Using these unbiased importance weights ensure that the reweighted training
loss is an unbiased estimate of the test loss.

However, as noted above, past work has shown that interpolating classifiers
trained with gradient descent on importance weighted exponentially-tailed
losses, such as the logistic loss
$\ell_{\text{log}}(z):=\log\left(1+\exp(-z)\right)$, the exponential loss
$\ell_{\text{exp}}(z):=\exp(-z)$, and the cross-entropy loss, ignore the
importance weights. For example, consider the case when the classifier is
linear $f_{\theta}(x)=x\cdot\theta$, the weights are $w_{1},\ldots,w_{n}>0$,
and the reweighted loss function is
$\widehat{L}(\theta)=\sum_{i=1}^{n}w_{i}\ell_{\text{log}}(y_{i}x_{i}\cdot\theta)$.
[XYR20] showed that if the data is linearly separable then the iterates of
gradient descent converge in direction to the $\ell_{2}$-maximum margin
classifier,

$\displaystyle\widehat{\theta}_{\mathsf{MM}}:=\operatorname*{arg\,max}_{\theta:\lVert\theta_{2}\rVert=1}\left\\{\gamma\;:\;y_{i}x_{i}\cdot\theta\geq\gamma\;\text{for
all }i\in[n]\right\\}.$ (1)

Observe that the maximum margin classifier does not depend on the set of
importance weights $(w_{1},\ldots,w_{n})$ and hence may suffer large test
error when there is distribution shift. [XYR20] further showed that when
separability assumptions hold, non-linear classifiers (like multilayer neural
networks) trained with gradient descent on exponentially-tailed losses are
also unaffected by importance weights.

We initiate a study of polynomially-tailed losses in the distribution shift
setting and show that they have improved behavior with respect to importance
weighting even when the model is overparameterized. Given parameters
$\alpha>0$ and $\beta\in\mathbb{R}$ define the polynomially-tailed loss as
follows:

$\displaystyle\ell_{\alpha,\beta}(z):=\begin{cases}\ell_{\mathsf{left}}(z)\qquad&\text{if
}z<\beta\\\ \frac{1}{\left[z-(\beta-1)\right]^{\alpha}}\qquad&\text{if
}z\geq\beta,\end{cases}$

where $\ell_{\mathsf{left}}$ is any loss function such that the overall loss
function $\ell_{\alpha,\beta}$ is convex, differentiable and strictly
decreasing. Several natural choices for $\ell_{\mathsf{left}}$ include the
scaled logistic ($c_{1}\log(1+\exp(-c_{2}z))$), exponential
($c_{1}\exp(-c_{2}z)$) or linear $(-c_{1}z+c_{2})$ losses.

Given a training dataset $\left\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\right\\}$
and a set of weights $w_{1},\ldots,w_{n}\geq 0$ we let

$\displaystyle\widehat{L}_{\alpha,\beta}(f_{\theta}):=\sum_{i=1}^{n}w_{i}\ell_{\alpha,\beta}(y_{i}f_{\theta}(x_{i}))$

be the reweighted empirical loss on this dataset.

##### Notation.

Given a vector $v$, let $\lVert v\rVert$ denote its Euclidean norm. For any
$j\in\mathbb{N}$, we denote the set $\\{1,\ldots,j\\}$ by $[j]$. A random
variable $\xi$ is $1$-sub-Gaussian if for any $\lambda\in\mathbb{R}$,
$\mathbb{E}\left[e^{\lambda\xi}\right]\leq e^{\lambda^{2}/2}$.

##  4 Theoretical Results

In this section, we present several theoretical results that justify the use
of polynomially-tailed losses in conjunction with importance weights to handle
distribution shifts. To let the analysis proceed, we restrict our theoretical
study to linear classifiers, $f_{\theta}(x)=x\cdot\theta$, for some
$\theta\in\mathbb{R}^{d}$.

First, in Section 4.1 we shall characterize the limiting direction of gradient
descent on reweighted polynomially-tailed losses and show that this direction
depends on both the weights as well as the datapoints. Next, in Section 4.2,
we upper bound the test error of this limiting solution in a label shift
setting. We also show that choosing weights that are obtained by
exponentiating the unbiased importance weights helps in reducing the test
error. Finally, in this label shift setting, we show that the maximum margin
classifier suffers an error that is at least $1/8$.

###  4.1 Implicit Bias of Gradient Descent on Polynomially-Tailed Losses

We begin by presenting a result that characterizes the implicit bias of
gradient descent on reweighted polynomially-tailed losses for linearly
separable classification. Understanding this situation is a key first step, as
gradient descent for separable linear classification is often used as a
simplified model to theoretically characterize the behavior of
overparameterized models such as neural networks [Sou+18, JT19, Nac+19, LL19,
JT20].

Given a linearly separable dataset $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$, we
let $z_{i}:=y_{i}x_{i}$. We shall analyze the iterates of gradient descent
with step-size $\eta>0$ and initial iterate $\theta^{(0)}\in\mathbb{R}^{d}$:

$\displaystyle\theta^{(t+1)}=\theta^{(t)}-\eta\nabla\widehat{L}_{\alpha,\beta}(\theta^{(t)}),\quad\text{for
}t\in\\{0,1,\ldots\\}.$

Define the direction

$\displaystyle\widehat{\theta}_{\alpha}:=\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert=1}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{(z_{i}\cdot\theta)^{\alpha}},\hskip
3.61371pt\text{s.t.}\quad z_{i}\cdot\theta>0,\quad\text{for all
}i\in[n]\right\\}.$ (2)

The following proposition characterizes the limiting direction of gradient
descent iterates. propositionimplicitbias Suppose that the data is linearly
separable. For any $\alpha>0$, $\beta\in\mathbb{R}$, any initial point
$\theta^{(0)}\in\mathbb{R}^{d}$, and for all small enough step-sizes $\eta$
the direction of the gradient descent iterates satisfy the following:

$\displaystyle\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}\to\widehat{\theta}_{\alpha}.$

The proof is presented in Appendix A. This proof relies on the recent result
by [Ji+20] who relate the limiting direction of gradient descent on the
unregularized loss to the limiting solution of a norm-constrained loss
minimization problem, where the limit is taken with respect to the norm
constraint.

Note that, unlike the maximum margin classifier, it is immediately clear that
this limiting direction $\widehat{\theta}_{\alpha}$ depends on the weights
$w_{1},\ldots,w_{n}$. As one would intuitively expect, the direction
$\widehat{\theta}_{\alpha}$ tries to achieve a larger margin
$z_{i}\cdot\theta$ on points with larger weights $w_{i}$. This behavior is
also apparent in the simulation in the rightmost panel in Figure 1, where
upweighting points in the minority class helps to learn a classifier that is
similar in direction to the Bayes optimal classifier for the problem.

Our limiting direction $\widehat{\theta}_{\alpha}$ has the interesting
property that it does not depend on several quantities: the initial point
$\theta^{(0)}$, the properties of $\ell_{\mathsf{left}}$, and the “switchover”
point $\beta$. Linear separability ensures that in the limit, the margin on
each point is much larger than $\beta$, and so the loss of each point is in
the polynomial tail of part of $\ell_{\alpha,\beta}$.

###  4.2 Generalization Analysis

The result in the previous subsection shows that the asymptotic classifier
learnt by gradient descent, $\widehat{\theta}_{\alpha}$ respects importance
weights. However, this does not demonstrate that using polynomially-tailed
losses leads to classifiers with lower test error compared to using
exponentially-tailed losses.

To answer this more 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 [CL21, WT21, LR21, CGB21]. 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.

Under these assumptions, we derive upper bounds on the error incurred by
$\widehat{\theta}_{1}$, the limiting direction of gradient descent of
polynomially tailed losses with $\alpha=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 $\alpha$.) 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 Setting for Generalization Analysis

Here we formally describe the setting of our generalization analysis. We let
$C\geq 1$ and $0<\widetilde{C}\leq 1$ denote positive absolute constants,
whose value is fixed throughout the remainder of the paper. We will use
$c,c^{\prime},c_{1},\ldots$ to denote “local” positive constants, which may
take different values in different contexts.

The training dataset
$\mathcal{S}:=\left\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\right\\}$ has $n$
independently drawn samples. The conditional distribution of the features
given the label is

$\displaystyle x\mid\\{y=1\\}$ $\displaystyle=\mu_{1}+Uq$ $\displaystyle
x\mid\\{y=-1\\}$ $\displaystyle=\mu_{2}+Uq,$

where $\mu_{1}\cdot\mu_{2}=0$, $\lVert\mu_{1}\rVert=\lVert\mu_{2}\rVert$, $U$
is an arbitrary orthogonal matrix, and $q$ is a random variable such that

  * •

its entries are $1$-sub-Gaussian and independent, and

  * •

$\mathbb{E}\left[\lVert q\rVert^{2}\right]\geq\widetilde{C}d$.

We note that in past work that studied this setting [CL21, WT21, CGB21], the
cluster centers were chosen to be opposite one another $\mu_{1}=-\mu_{2}$.
Here, since our goal here is to study a label shift setting we consider the
cluster centers $\mu_{1}$ and $\mu_{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 $\mathcal{P}:=\left\\{i\in[n]:y_{i}=1\right\\}$ to be the set of
indices corresponding to the positive labels and
$\mathcal{N}:=\left\\{i\in[n]:y_{i}=-1\right\\}$ to be the set of indices
corresponding to the negative labels. As stated above, we will focus on the
case where $|\mathcal{P}|\gg|\mathcal{N}|\geq 1$. Let
$\tau:=\frac{|\mathcal{P}|}{|\mathcal{N}|}\geq 1$ be the ratio between the
number of positive and negative samples.

The test distribution $\mathsf{P}_{\mathsf{test}}$ is balanced. That is, if
$(x,y)\sim\mathsf{P}_{\mathsf{test}}$, then
$\mathbb{P}\left[y=1\right]=\mathbb{P}\left[y=-1\right]=1/2$ and $x\mid y$
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

$\displaystyle w_{i}=\begin{cases}1\qquad&\text{if }i\in\mathcal{P}\\\
w\qquad&\text{if }i\in\mathcal{N}.\end{cases}$

##### Assumptions.

Given a failure probability $0<\delta<1/C$, we make the following assumptions
on the parameters of the problem:

  1. 1.

Number of samples $n\geq C\log(1/\delta)$.

  2. 2.

Norm of the means
$\lVert\mu\rVert^{2}:=\lVert\mu_{1}\rVert^{2}=\lVert\mu_{2}\rVert^{2}\geq
Cn^{2}\log(n/\delta)$.

  3. 3.

Dimension $d\geq Cn\lVert\mu\rVert^{2}$.

Our assumptions allow for large overparameterization, where the dimension $d$
scales polynomially with the number of samples $n$.

####  4.2.2 Upper Bound for the Reweighted Polynomially-Tailed Loss Classifier

First, we shall prove an upper bound on the test error of the solution learnt
by gradient descent on the reweighted polynomially-tailed loss. Under the
choice of weights described above, by equation (2)

$\displaystyle\widehat{\theta}_{1}=\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert=1}\sum_{i\in\mathcal{P}}\frac{1}{z_{i}\cdot\theta}+\sum_{i\in\mathcal{N}}\frac{w}{z_{i}\cdot\theta},\hskip
14.45377pt\text{s.t.}\quad z_{i}\cdot\theta>0,\quad\text{for all }i\in[n],$

where $z_{i}=y_{i}x_{i}$ as defined previously. The following theorem provides
an upper bound on the test error of $\widehat{\theta}_{1}$ and specifies a
range of values for the weight $w$. theorempolygenbound For any
$0<\widetilde{C}\leq 1$, there is a constant $c$ such that, for all large
enough $C$ and for any $0<\delta<1/C$, under the assumptions of this
subsection the following holds. If the weight

$\frac{\tau^{3}}{2}\leq w\leq 2\tau^{3},$

then with probability at least $1-\delta$, training on $\mathcal{S}$ produces
a classifier $\widehat{\theta}_{1}$ satisfying:

$\displaystyle\mathsf{TestError}[\widehat{\theta}_{1}]=\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}\left(\widehat{\theta}_{1}\cdot
x\right)\neq
y\right]\leq\exp\left(-\frac{cn}{\tau}\frac{\lVert\mu\rVert^{4}}{d}\right).$

This theorem is proved in Appendix B. To prove this theorem, we first show
that the data is linearly separable under our assumptions and hence by the
implicit bias results of Proposition 4.1 our upper bound is equivalent to
bounding the test error of the limiting iterate of gradient descent on our
reweighted loss. The next step is to 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 $\mu_{1}$ and $-\mu_{2}$ which then proves our bound on the test error
via a standard Hoeffding bound.

If we consider a regime where $d$ and $n$ are growing simultaneously, then the
test error goes down to zero if the norm of the cluster means
$\lVert\mu\rVert$ grows faster than $d^{1/4}$, regardless of the level of
imbalance in the training data as $\tau<n$. Briefly note that in setting with
balanced data ($\tau=1$), the bound on the test error here matches the bound
obtained for the maximum margin classifier in [CL21, WT21, CGB21] (although
these bounds are not directly comparable as the setting here is slightly
modified for a label shift). The impossibility result by [Jin09] shows that
these previous results guarantee that learning occurs right up until the
information theoretic frontier ($\lVert\mu\rVert^{2}=\omega(\sqrt{d})$).

Finally, it is rather interesting to note that the theorem requires the weight
$w$ to scale with $\tau^{3}$, instead of $\tau$, 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 in order to suffer low
test error it 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 $\frac{\tau}{w^{1/3}}$.
Thus choosing $w$ to scale with $\tau^{3}$ ensures that the gradients are
balanced across both groups. We also verify this in our simulations in Figure
2, and find that choosing $w=\tau^{3}$ ensures that the test error is equal
across both classes leading to low overall test error.

(a)

(b)

Figure 2: A simulation study with class-conditional Gaussians, with
$d=10^{6}$, $\lVert\mu\rVert^{2}=d^{0.502}$ and $n=100$. The mean
$\mu_{1}=\lVert\mu\rVert e_{1}$ and $\mu_{2}=\lVert\mu\rVert e_{2}$, and
$q\sim\mathsf{N}(0,I_{d\times d})$. (Left) We plot the test error of
$\widehat{\theta}_{1}$ as $\tau$ varies for different choices of $w$, and also
for the maximum margin classifier. The choice $w=\tau^{3}$ leads to the lowest
error throughout, while $w=\tau$ also does well for small $\tau$. Both the
polynomially-tailed classifier with no importance weighting and the maximum
margin classifier suffer large test error. (Right) Here we fix the imbalance
ratio $\tau=10.1$, and study how the error of $\widehat{\theta}_{1}$ varies
with $w$. When $w=\tau^{3}$, the error on both the majority and minority
classes is almost equal, resulting in low overall test 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-tailed 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.
theoremmaxmarginlowerbound Let $q\sim\mathsf{N}(0,I_{d\times d})$. There exist
constants $c$ and $c^{\prime}$ such that, for all large enough $C$ and for any
$0<\delta<1/C$, under the assumptions of this subsection the following holds.
With probability at least $1-\delta$, training on $\mathcal{S}$ produces a
maximum margin classifier $\widehat{\theta}_{\mathsf{MM}}$ satisfying:

$\displaystyle\mathsf{TestError}[\widehat{\theta}_{\mathsf{MM}}]=\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}\left(\widehat{\theta}_{\mathsf{MM}}\cdot
x\right)\neq
y\right]\geq\frac{1}{2}\cdot\Phi\left(-\frac{c\sqrt{n}}{\tau}\cdot\frac{\lVert\mu\rVert^{2}}{\sqrt{d}}\right),$

where $\Phi$ is the Gaussian cdf. Furthermore, if the imbalance ratio
$\tau\geq c^{\prime}\frac{\sqrt{n}\lVert\mu\rVert^{2}}{\sqrt{d}}$ then with
probability at least $1-\delta$

$\displaystyle\mathsf{TestError}[\widehat{\theta}_{\mathsf{MM}}]\geq\frac{1}{8}.$

This theorem is proved in Appendix C. Intuitively, the lower bound holds
because when the imbalance is severe, the max-margin classifier essentially
ignores the samples in the minority class and overfits to the majority class.
Ignoring these negative samples results in a 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 a strict gap between
the performance of exponentially tailed and polynomially tailed losses under
distribution shifts. As a concrete example, consider the scaling where
$\lVert\mu\rVert^{2}=d^{\frac{1}{2}+\frac{1}{40}}$, $n=d^{\frac{1}{5}}$ and
$\tau=d^{\frac{3}{20}}\leq n$. For all large enough $d$, all our assumptions
are satisfied. Now since, $\sqrt{n}\lVert\mu\rVert^{2}>\sqrt{\tau d}$, Theorem
4.2.2 guarantees that the test error of $\widehat{\theta}_{1}\to 0$ as
$d\to\infty$. However, as $\tau=d^{\frac{3}{20}}\geq
c^{\prime}\lVert\mu\rVert^{2}\sqrt{n/d}=c^{\prime}d^{\frac{5}{40}}$, for all
large enough $d$, the test error of the maximum margin classifier is
guaranteed to be at least $1/8$. This degradation of the test error with
$\tau$ 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 a polynomially-tailed loss with $\beta=1$ and
$\ell_{\mathsf{left}}(z)=\log(1+e^{-z})/\log(1+e^{-1})$, ensuring that
$\ell_{\alpha,\beta}$ is continuous at transition $z=\beta$ when $\alpha=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 D. Though these nonlinear networks violate the assumptions of our
theory, polynomially-tailed loss with importance weights consistently improves
test accuracy for interpolating neural networks under distribution shift
compared to importance-weighted cross-entropy loss.

##### Imbalanced binary CIFAR10.

We construct our label shift dataset from the full CIFAR10 dataset. Similar to
[BL19], 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 [BL19] with random initializations for this dataset.

##### Subsampled CelebA.

For our subpopulation shift dataset, we use the CelebA with spurious
correlations dataset constructed by [Sag+19]. 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 our test set by
downsampling the original test to get group-balanced representation in the
test set, resulting in 180 examples for each group. Following [Sag+19], 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 accuracies on the test sets. We compare models trained with
our polynomially-tailed loss against those trained with the cross-entropy loss
which has exponential tails. Let $\overline{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 ($\overline{w}$)”, and biased weighting where we
exponentiate the weights, “IW ($\overline{w}^{c}$))”, increasing the ratio of
different weights. The third setting is inspired by our theory in Section 4
that shows biased importance weights can improve performance for polynomially-
tailed losses. For these experiments, we fixed $\alpha=1$ and set the
exponents to be the largest value that still allowed for stable optimization.
For CelebA, we exponentiate by $2$ and for CIFAR10 we exponentiate by $3/2$.
We run 10 seeds for each experiment setting. We compare the two losses via
paired one-sided Welch’s $t$-tests, pairing runs with the same random seed. We
report the exact numbers in Appendix D.

Figure 3: Polynomially-tailed loss versus cross-entropy loss on a label shift
dataset and a subpopulation 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-tailed loss. IW has little effect for cross-entropy.444 The
mean test accuracy for “No IW” with cross-entropy on CIFAR10 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 [BL19]
which used balanced training data and imbalanced test data.

Figure 4 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 to statistically significant gains over
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.2. However, 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 CIFAR10, we find a smaller gap
between polynomially-tailed losses and cross-entropy, partially due to a
substantially higher run-to-run variability in training. This variability does
not affect our main conclusion: exponentiated reweighting with polynomially
tailed losses still outperforms this at a significance level of $p=0.01$ even
with this noise level.

##### Early-stopping before models interpolate.

Prior works [Sag+19, BL19] found that adding regularization such as strong L2
regularization and early stopping can partially restore the effects of
importance weights at the cost of not interpolating the training set. As such,
we compare the performance of our polynomially-tailed loss against cross-
entropy when models are early-stopped, using the same settings as before. For
each run here, we select the model checkpoint with the best weighted
validation accuracy and evaluate the checkpoint on the test set. Figure 4
compares the test accuracies of the early-stopped models (IW-ES
($\overline{w}$), IW-ES ($\overline{w}^{c}$)) against reweighted models
trained past interpolation (IW ($\overline{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-tailed loss gives test accuracies
that are better than or similar to cross-entropy in all weighted loss
scenarios. The gain over cross-entropy is statistically significant in the
binary CIFAR10 runs. On subsampled CelebA, the polynomially-tailed loss with
squared weights attains the highest mean test accuracy out of all settings.

Figure 4: Polynomially-tailed loss versus cross-entropy loss on a label shift
dataset and a subpopulation 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 imbalanced binary CIFAR10.

###  5.2 Comparing against prior distribution shift methods

Figure 5: Our polynomially-tailed loss with exponentiated importance weights
is better than or competitive with state of the art methods designed to
address distribution shift. We tune all methods extensively using the same
validation set. We compare to cross entropy with undersampling (CE$+$US),
label-distribution-aware margin loss (LDAM), class-dependent temperatures loss
(CDT), logit-adjusted loss (LA), vector-scaling loss (VS), and the use of
distributionally robust optimization (DRO)

To place our method’s empirical performance in the context of prior works, we
extensively compare our method to state-of-the-art distribution shift methods.
On binary CIFAR10, we compare to label-distribution-aware margin (LDAM) loss
[Cao+19], class-dependent temperatures (CDT) loss [Ye+20], logit-adjusted (LA)
loss [Men+20], and vector-scaling (VS) loss [Kin+21]. 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 [Sag+19]
when combined with poly-tailed loss versus VS loss. 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. We grid search each method exhaustively, and report
results over 10 random initialization seeds. See Appendix D for more details
on our procedure and the best hyperparameters we found. Unlike in Section 5.1,
here we tune both the importance weight exponent _and_ $\alpha$ 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. Figure 5 shows that when $\alpha$
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_.

On binary CIFAR10, our poly-tailed loss performs comparably to LA loss and is
only 2% worse than VS loss in mean test accuracy with overlapping confidence
intervals. Note that at first, we grid searched VS loss across the published
hyperparameter ranges from [Kin+21], and it performed poorly (58.6% test
accuracy). After a more thorough grid search for VS loss, we found 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 hyperparameters) and was
beaten by 2% only after more extensive hyperparameter tuning on our part.

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. We emphasize that we expect poly loss with IW to perform well
on average test accuracy, and that poly-tailed with IW does not target worst
group accuracy directly in the training objective. However, in practice poly-
tailed loss with IW gives the best worst group accuracy out of all loss
functions when not using DRO (see Appendix D for worst group accuracies).

##  6 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-tailed
loss provably depends on the importance weights, unlike the maximum-margin
classifier recovered by an exponentially decaying loss function. From bounding
the generalization error of our loss function, we found a setting where
increasing the ratio of the weights improves the test accuracy. We empirically
corroborated these theoretical intuitions, finding that weighted polynomially-
tailed losses are also able to address distribution shift for interpolating
neural networks. 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.

##  Appendix A Proof of Proposition 4.1

First, we restate the statement of the proposition. *

Proof  Recall that the loss $\ell_{\alpha,\beta}$ is assumed to be convex,
strictly decreasing to zero and is differentiable. Define the minimizer of the
loss over a ball of radius $R$ as follows

$\displaystyle\theta_{R}=\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
R}\widehat{L}_{\alpha,\beta}(\theta).$

Under the assumptions of this proposition, we can invoke Theorem 1 by [Ji+20]
to get that

$\displaystyle\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}=\lim_{R\to\infty}\frac{\theta_{R}}{R}.$

We will therefore instead demonstrate that
$\lim_{R\to\infty}\frac{\theta_{R}}{R}=\widehat{\theta}_{\alpha}$ to establish
our claim.

First, note that the classifier $\theta_{R}$ is the minimizer of loss in a
ball of radius $R$, so there exists a $R_{0}$ with

$\widehat{L}_{\alpha,\beta}(\theta_{R_{0}})=\sum_{i\in[n]}w_{i}\ell_{\alpha,\beta}(z_{i}\cdot\theta_{R_{0}})\leq(\min_{i}w_{i})\ell_{\alpha,\beta}(\beta)$

such that for all $R>R_{0}$, each example is classified correctly by
$\theta_{R}$ and the margin $(z_{i}\cdot\theta_{R})$ on each example is at
least $\beta$. Therefore,

$\displaystyle\widehat{L}_{\alpha,\beta}(\theta_{R})=\sum_{i=1}^{n}w_{i}\ell_{\alpha,\beta}(z_{i}\cdot\theta_{R})=\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta_{R}-(\beta-1)\right]^{\alpha}}.$

Thus, for any radius $R>R_{0}$ we have

$\displaystyle\frac{\theta_{R}}{R}$
$\displaystyle=\frac{1}{R}\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
R}\widehat{L}_{\alpha,\beta}(\theta)$
$\displaystyle=\frac{1}{R}\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
R}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta-(\beta-1)\right]^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta\geq\beta$}\right\\}$
$\displaystyle=\frac{1}{R}\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
R}\left\\{\frac{1}{R^{\alpha}}\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\left(\frac{\theta}{R}\right)-\frac{\beta-1}{R}\right]^{\alpha}},\hskip
14.45377pt\mbox{s.t.,
$z_{i}\cdot\left(\frac{\theta}{R}\right)\geq\frac{\beta}{R}$}\right\\}$
$\displaystyle=\frac{1}{R}\times\left(R\cdot\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
1}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta-\frac{\beta-1}{R}\right]^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta\geq\frac{\beta}{R}$}\right\\}\right).$

Now taking the limit $R\to\infty$ we get that

$\displaystyle\lim_{R\to\infty}\frac{\theta_{R}}{R}$
$\displaystyle=\lim_{R\to\infty}\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
1}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta-\frac{\beta-1}{R}\right]^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta\geq\frac{\beta}{R}$}\right\\}$
$\displaystyle\overset{(i)}{=}\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
1}\left\\{\lim_{R\to\infty}\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta-\frac{\beta-1}{R}\right]^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta\geq\frac{\beta}{R}$}\right\\}$
$\displaystyle=\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
1}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{\left(z_{i}\cdot\theta\right)^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta\geq 0$}\right\\}$
$\displaystyle\overset{(ii)}{=}\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
1}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{\left(z_{i}\cdot\theta\right)^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta>0$}\right\\}$
$\displaystyle=\widehat{\theta}_{\alpha}.$

where $(i)$ follows since for every $R$ the function

$\displaystyle\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta-\frac{\beta-1}{R}\right]^{\alpha}}$

is convex and continuous, and therefore

$\displaystyle\operatorname*{arg\,min}_{\theta:\lVert\theta\rVert\leq
1}\left\\{\sum_{i=1}^{n}\frac{w_{i}}{\left[z_{i}\cdot\theta-\frac{\beta-1}{R}\right]^{\alpha}},\hskip
14.45377pt\mbox{s.t., $z_{i}\cdot\theta\geq\frac{\beta}{R}$}\right\\}$

has a unique minimizer (since the objective function is strictly convex, and
the constraint set is convex and compact), and is a continuous map by Berge’s
maximum theorem [BD90, see, e.g.,]. Thus, it is possible to switch the order
of the limit and the $\operatorname*{arg\,min}$. Equation $(ii)$ follows since
the data is linearly separable, so there exists a $\theta$ such that
$z_{i}\cdot\theta>0$ for all $i$ which has finite objective value.

Therefore,

$\displaystyle\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}=\lim_{R\to\infty}\frac{\theta_{R}}{R}$
$\displaystyle=\widehat{\theta}_{\alpha},$

which finishes our proof.

##  Appendix B Proof of Theorem 4.2.2

In this section, we will prove an upper bound on the test error
$\widehat{\theta}_{1}$, which is the classifier learnt by gradient descent
with the importance weighted polynomially-tailed loss that decays as $1/z$. By
Proposition 4.1, we know the choice of $\ell_{\mathsf{left}}$ and $\beta$ does
not affect the implicit bias of gradient descent, hence here, for the sake of
convenience, we shall use the specific loss function

$\displaystyle\ell_{1,\beta}(z):=\begin{cases}-(z-\beta)+1\qquad&\text{if
}z<\beta\\\ \frac{1}{z-(\beta-1)}\qquad&\text{if }z\geq\beta,\end{cases}$

with $\beta=1-wn<0$. It can be easily checked that this loss function is
convex, differentiable and monotonically decreasing.

We want to bound the test error of $\widehat{\theta}_{1}$, however, in light
of Proposition 4.1 we will instead bound the test error of the limiting
iterate of gradient descent starting from
$\theta^{(0)}=8w^{2/3}n\left(\mu_{1}-w^{1/3}\mu_{2}\right)$ with step-size
$\eta>0$ (again by the implicit bias of gradient descent is not affected by
the choice of the initial point):

$\displaystyle\theta^{(t+1)}=\theta^{(t)}-\eta\nabla\widehat{L}(\theta^{(t)}),$

where

$\displaystyle\widehat{L}(\theta)=\sum_{i\in\mathcal{P}}\ell_{1,\beta}(z_{i}\cdot\theta)+w\sum_{i\in\mathcal{N}}\ell_{1,\beta}(z_{i}\cdot\theta).$

Recall that if the step-size is small enough then Proposition 4.1 guarantees
that
$\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}=\widehat{\theta}_{1}$.
In this section we will simply let $\ell$ denote $\ell_{1,\beta}$ and also use
the shorthands $\ell_{i}^{(t)}:=\ell(z_{i}\cdot\theta^{(t)})$ and
$\ell^{\prime(t)}_{i}:=\ell^{\prime}(z_{i}\cdot\theta^{(t)})$.

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 a lemma that upper bounds
the test error using Hoeffding’s inequality.

######  Lemma B.1.

There is a positive absolute constant $c$ such that

$\displaystyle\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}\left(\theta\cdot
x\right)\neq
y\right]\leq\frac{1}{2}\left[\exp\left(-c\frac{(\theta\cdot\mu_{1})^{2}}{\lVert\theta\rVert^{2}}\right)+\exp\left(-c\frac{(\theta\cdot\mu_{2})^{2}}{\lVert\theta\rVert^{2}}\right)\right].$

This lemma follows by mirroring the proof of [CL21] which in turn follows by a
simple application of Hoeffding’s inequality [Ver18].

Next we have a 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\geq 1$ and $0<\widetilde{C}\leq 1$ were defined
above in Section 4.2.

######  Lemma B.2.

For all $0<\widetilde{C}\leq 1$, there is a $c\geq 1$ such that, for all large
enough $C$, with probability $1-\delta$ over the draw of the samples the
following events simultaneously occur:

  1. E.1

For all $k\in[n]$

$\displaystyle\frac{d}{c}\leq\lVert z_{k}\rVert^{2}\leq cd.$

  2. E.2

For all $i\in\mathcal{P}$ and $j\in\mathcal{N}$,

$\displaystyle|z_{i}\cdot z_{j}|\leq c\sqrt{d\log(n/\delta)}.$

  3. E.3

For all $i\neq j\in[n]$,

$\displaystyle\lvert z_{i}\cdot
z_{j}\rvert<c(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}).$

  4. E.4

For all $k\in\mathcal{P}$,

$\displaystyle\lvert\mu_{1}\cdot
z_{k}-\lVert\mu\rVert^{2}\rvert<\lVert\mu\rVert^{2}/2.$

  5. E.5

For all $k\in\mathcal{N}$,

$\displaystyle\lvert(-\mu_{2})\cdot
z_{k}-\lVert\mu\rVert^{2}\rvert<\lVert\mu\rVert^{2}/2.$

  6. E.6

For all $k\in\mathcal{N}$,

$\displaystyle\lvert\mu_{1}\cdot
z_{k}\rvert<c\lVert\mu\rVert\sqrt{\log(n/\delta)}.$

  7. E.7

For all $k\in\mathcal{P}$,

$\displaystyle\lvert\mu_{2}\cdot
z_{k}\rvert<c\lVert\mu\rVert\sqrt{\log(n/\delta)}.$

  8. E.8

The samples are linearly separable.

Proof  We shall prove that each of the ten parts hold with probability at
least $1-\delta/10$ and take a union bound to prove our lemma. Under the
assumptions of this lemma, Parts (1), (3)-(5) and (8) can be shown to hold
with the required probability by invoking [CL21]. 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\in\mathcal{P}$,
$z_{i}=\mu_{1}+Uq_{i}$, and for all $i\in\mathcal{N}$, $z_{i}=\mu_{2}+Uq_{2}$.
Therefore, for any $i\in\mathcal{P}$ and $j\in\mathcal{N}$, since
$\mu_{1}\cdot\mu_{2}=0$,

$\displaystyle|z_{i}\cdot z_{j}|$
$\displaystyle=\mu_{1}\cdot(Uq_{j})+\mu_{2}\cdot(Uq_{i})+q_{i}\cdot q_{j}$
$\displaystyle\leq|\mu_{1}\cdot(Uq_{j})|+|\mu_{2}\cdot(Uq_{i})|+|q_{i}\cdot
q_{j}|$ $\displaystyle=|(U^{\top}\mu_{1})\cdot q_{j}|+|(U^{\top}\mu_{2})\cdot
q_{i}|+|q_{i}\cdot q_{j}|.$ (3)

We will show that each of these terms is small with high probability for all
pairs $i\in\mathcal{P}$ and $j\in\mathcal{N}$.

For the first two terms, note that by Hoeffding’s inequality [Ver18]

$\displaystyle\mathbb{P}\left[\lvert(U^{\top}\mu_{1})\cdot
q_{j}\rvert>\frac{c\lVert\mu\rVert\sqrt{\log(n/\delta)}}{3}\right]$
$\displaystyle<2\exp\left(-\frac{c_{1}c^{3}}{9}\frac{\lVert\mu\rVert^{2}\log(n/\delta)}{\lVert\mu\rVert^{2}}\right)$
$\displaystyle=2\exp\left(-\frac{c_{1}c^{3}}{9}\log(n/\delta)\right)$
$\displaystyle=2\left(\frac{\delta}{n}\right)^{c_{1}c^{3}/9}$
$\displaystyle\leq\frac{\delta}{30n},$

where the last inequality follows since the constant $c\geq 1$ can be chosen
to be large enough and because $\delta<1/C$ for a large enough constant $C$.
Therefore, by taking a union bound over all $j\in\mathcal{N}$

$\displaystyle\mathbb{P}\left[\exists
j\in\mathcal{N},\;\lvert(U^{\top}\mu_{1})\cdot
q_{j}\rvert>\frac{c\lVert\mu\rVert\sqrt{\log(n/\delta)}}{3}\right]<\frac{\delta}{30}.$
(4)

Using an analogous argument we can also show that

$\displaystyle\mathbb{P}\left[\exists
i\in\mathcal{P},\;\lvert(U^{\top}\mu_{2})\cdot
q_{i}\rvert>\frac{c\lVert\mu\rVert\sqrt{\log(n/\delta)}}{3}\right]<\frac{\delta}{30}.$
(5)

Next, using [CL21] we get that

$\mathbb{P}\left[\exists i\neq j\in[n],\;|q_{i}\cdot
q_{j}|>\frac{c\sqrt{d\log(n/\delta)}}{3}\right]\leq\frac{\delta}{30}.$ (6)

Combining inequalities (3)-(6) we get that for all $i\in\mathcal{P}$ and
$j\in\mathcal{N}$ with probability at least $1-\delta/10$

$\displaystyle|z_{i}\cdot
z_{j}|\leq\frac{2c\lVert\mu\rVert\sqrt{\log(n/\delta)}}{3}+\frac{c\sqrt{d\log(n/\delta)}}{3}\leq
c\sqrt{d\log(n/\delta)},$

where the last inequality follows since by assumption $d\geq
Cn\lVert\mu\rVert^{2}$ and because $C$ is large enough. This completes the
proof of this part.

Proof of Part (6): For any $k\in\mathcal{N}$, $z_{k}=\mu_{2}+Uq_{k}$. Recall
that $\mu_{1}\cdot\mu_{2}=0$, thus

$\displaystyle|\mu_{1}\cdot z_{k}|=|\mu_{1}\cdot(Uq_{k})|.$

Invoking inequality (4) proves that this part holds with probability at least
$1-\delta/10$.

Proof of Part (7): This follows by an analogous argument as in the previous
part.

We continue by defining a good event that we will work under for the rest of
the proof.

######  Definition B.3.

If the training dataset $\mathcal{S}$ satisfies all the conditions specified
in Lemma B.2 then we call it a _good run_.

Going forward in this section we 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-tailed part throughout training.

######  Lemma B.4.

Recall that $\theta^{(0)}=8w^{2/3}n(\mu_{1}-w^{1/3}\mu_{2})$, and that
$w_{i}=1$ if $i\in\mathcal{P}$ and $w_{i}=w$ if $i\in\mathcal{N}$. On a good
run, for all $i\neq j\in[n]$

$\displaystyle\frac{\ell_{i}^{(0)}}{\ell_{j}^{(0)}}$ $\displaystyle\leq
8\left(\frac{w_{j}}{w_{i}}\right)^{1/3}.$

Furthermore, if the step-size $\eta$ is sufficiently small then on a good run,
for all $t\in\\{0,1,\ldots\\}$ and for all $i\in[n]$

$\displaystyle\ell_{i}^{(t)}=\frac{1}{z_{i}\cdot\theta^{(t)}-(\beta-1)}.$

Proof  Consider an $i\in\mathcal{P}$ then

$\displaystyle
z_{i}\cdot\theta^{(0)}=8w^{2/3}n\left(z_{i}\cdot\mu_{1}-w^{1/3}z_{i}\cdot\mu_{2}\right)$
$\displaystyle\overset{(i)}{\leq}8w^{2/3}n\left(\frac{3\lVert\mu\rVert^{2}}{2}+c_{1}w^{1/3}\lVert\mu\rVert\sqrt{\log(n/\delta)}\right)$
$\displaystyle\leq
12w^{2/3}n\lVert\mu\rVert^{2}\left[1+\frac{2c_{1}w^{1/3}\sqrt{\log(n/\delta)}}{3\lVert\mu\rVert}\right]$
$\displaystyle\overset{(ii)}{\leq}16w^{2/3}n\lVert\mu\rVert^{2},$

where $(i)$ follows by Lemma B.2 and $(ii)$ follows since
$\lVert\mu\rVert^{2}\geq Cn^{2}\log(n/\delta)\geq
C\tau^{2}\log(n/\delta)\geq\frac{C}{2^{2/3}}w^{2/3}\log(n/\delta)$ for a large
enough constant $C$. Similarly, we also have the lower bound

$\displaystyle z_{i}\cdot\theta^{(0)}$
$\displaystyle=8w^{2/3}n\left(z_{i}\cdot\mu_{1}-w^{1/3}z_{i}\cdot\mu_{2}\right)$
$\displaystyle\geq
8w^{2/3}n\left(\frac{\lVert\mu\rVert^{2}}{2}-c_{1}w^{1/3}\lVert\mu\rVert\sqrt{\log(n/\delta)}\right)\geq
4w^{2/3}n\lVert\mu\rVert^{2}\left[1-\frac{2c_{1}w^{1/3}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right].$

Recall from the definition of the loss that we set $\beta=1-nw$. Now again
since $\lVert\mu\rVert^{2}\geq\frac{C}{2^{2/3}}w^{2/3}\log(n/\delta)$, and
because we choose $\beta=1-nw$, we infer that

$\displaystyle
z_{i}\cdot\theta^{(0)}-(\beta-1)\geq\frac{8w^{2/3}n\lVert\mu\rVert^{2}}{3}-nw\geq
2w^{2/3}n\lVert\mu\rVert^{2}.$

Since the margin of the point is larger than $(\beta-1)$ therefore by the
definition of the loss function above we have that

$\displaystyle\ell_{i}^{(0)}=\frac{1}{z_{i}\cdot\theta^{(0)}-(\beta-1)}$

and hence

$\displaystyle\frac{1}{16w^{2/3}n\lVert\mu\rVert^{2}}\leq\ell_{i}^{(0)}$
$\displaystyle\leq\frac{1}{2w^{2/3}n\lVert\mu\rVert^{2}}.$ (7)

By mirroring the logic we can also prove that for all $j\in\mathcal{N}$

$\displaystyle\frac{1}{16wn\lVert\mu\rVert^{2}}\leq\ell_{j}^{(0)}$
$\displaystyle\leq\frac{1}{2wn\lVert\mu\rVert^{2}}.$ (8)

By combining equations (7) and (8) we immediately get that

$\displaystyle\frac{\ell_{i}^{(0)}}{\ell_{j}^{(0)}}$ $\displaystyle\leq
8\left(\frac{w_{j}}{w_{i}}\right)^{1/3}.$

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 $\ell_{i}^{(t)}$ is equal to the polynomial
loss function. Note that

$\displaystyle\widehat{L}(\theta^{(0)})=\sum_{i\in\mathcal{P}}\ell_{i}^{(0)}+w\sum_{i\in\mathcal{N}}\ell_{i}^{(0)}$
$\displaystyle\leq\frac{|\mathcal{P}|}{2w^{2/3}n\lVert\mu\rVert^{2}}+\frac{w|\mathcal{N}|}{2wn\lVert\mu\rVert^{2}}\leq\frac{wn}{2wn\lVert\mu\rVert^{2}}\leq
1/2.$ (9)

This proves that $\ell_{i}^{(0)}\leq 1/2$ for all $i\in[n]$. By [Ji+20] we
know that if the step-size is small enough then the sequence
$\\{\widehat{L}(\theta^{(t)})\\}$ is non-increasing. Hence, we have that
$\ell_{i}^{(t)}\leq 1/2$ for all $t\in\\{0,1,\ldots\\}$ and for all samples.
This wraps up our proof.
The next lemma lower bounds the inner product between the normalized gradient
descent iterates, and $\mu_{1}$ and $\mu_{2}$.

######  Lemma B.5.

Let $c$ and $c^{\prime}$ be absolute constants. Then, on a good run, for any
$t\in\left\\{0,1,\ldots\right\\}$

$\displaystyle\frac{\mu_{1}\cdot\theta^{(t+1)}}{\lVert\theta^{(t+1)}\rVert}$
$\displaystyle\geq\frac{\mu_{1}\cdot\theta^{(0)}}{\lVert\theta^{(t+1)}\rVert}+\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c\sqrt{d}}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]\times$
$\displaystyle\hskip
72.26999pt\frac{\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c^{\prime}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right]}{\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}$

and

$\displaystyle\frac{\mu_{2}\cdot\theta^{(t+1)}}{\lVert\theta^{(t+1)}\rVert}$
$\displaystyle\geq\frac{\mu_{2}\cdot\theta^{(0)}}{\lVert\theta^{(t+1)}\rVert}+\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c\sqrt{d}}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]\times$
$\displaystyle\hskip
72.26999pt\frac{\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c^{\prime}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}\right]}{\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}.$

Proof  Let us prove the first claim for the inner product with $\mu_{1}$. The
second claim regarding $\mu_{2}$ shall follow analogously. For any
$t\in\\{0,1,\ldots\\}$, by the definition of the gradient descent step, we
have that

$\displaystyle\mu_{1}\cdot\theta^{(t+1)}$
$\displaystyle=\mu_{1}\cdot\theta^{(t)}+\eta\sum_{i\in\mathcal{P}}w_{i}\mu_{1}\cdot
z_{i}\left(-\ell^{\prime(t)}_{i}\right)+\eta\sum_{i\in\mathcal{N}}w_{i}\mu_{1}\cdot
z_{i}\left(-\ell^{\prime(t)}_{i}\right).$

Note that by the definition of the loss function we have that
$-\ell^{\prime(t)}_{i}\geq 0$ for all $t$ and all $i$. Thus by Parts (1) and
(6) of Lemma B.2 we get that

$\displaystyle\mu_{1}\cdot\theta^{(t+1)}$
$\displaystyle\geq\mu_{1}\cdot\theta^{(t)}+\frac{\eta\lVert\mu\rVert^{2}}{2}\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(t)}_{i}-c_{1}\eta\lVert\mu\rVert\sqrt{\log(n/\delta)}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}$
$\displaystyle=\mu_{1}\cdot\theta^{(t)}+\frac{\eta\lVert\mu\rVert^{2}}{2}\sum_{i\in[n]}-w_{i}\ell^{\prime(t)}_{i}-\frac{\eta\lVert\mu\rVert^{2}}{2}\left(1+\frac{c_{1}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}$
$\displaystyle=\mu_{1}\cdot\theta^{(t)}+\frac{\eta\lVert\mu\rVert^{2}}{2}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(t)}_{i}-\frac{c_{1}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}\right],$

where $c_{1}$ is the constant from Lemma B.2. Unrolling this inequality over
$t$ steps we have that

$\displaystyle\mu_{1}\cdot\theta^{(t+1)}$
$\displaystyle=\mu_{1}\cdot\theta^{(0)}+\frac{\eta\lVert\mu\rVert^{2}}{2}\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c_{1}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right].$
(10)

On the other hand, by the triangle inequality we know that

$\displaystyle\lVert\theta^{(t+1)}\rVert$
$\displaystyle\leq\lVert\theta^{(t)}\rVert+\eta\lVert\nabla\widehat{L}(\theta^{(t)})\rVert$
$\displaystyle=\lVert\theta^{(t)}\rVert+\eta\left\lVert\sum_{i\in[n]}z_{i}(-w_{i}\ell^{\prime(t)}_{i})\right\rVert$
$\displaystyle\leq\lVert\theta^{(t)}\rVert+\eta\left\lVert\sum_{i\in\mathcal{P}}z_{i}(-\ell^{\prime(t)}_{i})\right\rVert+\eta
w\left\lVert\sum_{i\in\mathcal{N}}z_{i}(-\ell^{\prime(t)}_{i})\right\rVert.$
(11)

Now note that

$\displaystyle\left\lVert\sum_{i\in\mathcal{P}}z_{i}(-\ell^{\prime(t)}_{i})\right\rVert^{2}$
$\displaystyle=\sum_{i\in\mathcal{P}}(\ell^{\prime(t)}_{i})^{2}\lVert
z_{i}\rVert^{2}+\sum_{i\neq
j\in\mathcal{P}}\ell^{\prime(t)}_{i}\ell^{\prime(t)}_{j}(z_{i}\cdot z_{j})$
$\displaystyle\overset{(i)}{\leq}c_{1}\left[\sum_{i\in\mathcal{P}}(-\ell^{\prime(t)}_{i})^{2}d+\sum_{i\neq
j\in\mathcal{P}}\ell^{\prime(t)}_{i}\ell^{\prime(t)}_{j}(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)})\right]$
$\displaystyle\overset{(ii)}{\leq}c_{1}\left(\max_{j\in\mathcal{P}}-\ell^{\prime(t)}_{j}\right)\left[d\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}+|\mathcal{P}|(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)})\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}\right]$
$\displaystyle=c_{1}\left(\max_{j\in\mathcal{P}}-\ell^{\prime(t)}_{j}\right)(d+|\mathcal{P}|\lVert\mu\rVert^{2}+|\mathcal{P}|\sqrt{d\log(n/\delta)})\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}$
$\displaystyle\overset{(iii)}{\leq}c_{2}\frac{d}{|\mathcal{P}|}\left(\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}\right)^{2}$

where $(i)$ follows by using Part (1) and Part (3) of Lemma B.2, $(ii)$
follows since $-\ell^{\prime(t)}_{j}$ is positive for all $j\in[n]$, and
$(iii)$ follows since by assumption $d\geq Cn\lVert\mu\rVert^{2}$ and
$\lVert\mu\rVert^{2}\geq Cn^{2}\log(n/\delta)$ for a large enough constant
$C$. Hence we have that

$\displaystyle\left\lVert\sum_{i\in\mathcal{P}}z_{i}(-\ell^{\prime(t)}_{i})\right\rVert$
$\displaystyle\leq\sqrt{c_{2}\frac{d}{|\mathcal{P}|}}\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}.$

Similarly, one can also show that

$\displaystyle\left\lVert\sum_{i\in\mathcal{N}}z_{i}(-\ell^{\prime(t)}_{i})\right\rVert$
$\displaystyle\leq\sqrt{c_{2}\frac{d}{|\mathcal{N}|}}\sum_{i\in\mathcal{N}}-\ell^{\prime(t)}_{i}.$

Applying these bounds in inequality (11) we get that

$\displaystyle\lVert\theta^{(t+1)}\rVert$
$\displaystyle\leq\lVert\theta^{(t)}\rVert+\eta\left[\sqrt{c_{2}\frac{d}{|\mathcal{P}|}}\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}+w\sqrt{c_{2}\frac{d}{|\mathcal{N}|}}\sum_{i\in\mathcal{N}}-\ell^{\prime(t)}_{i}\right]$
$\displaystyle\leq\lVert\theta^{(t)}\rVert+\eta\left[\sqrt{c_{2}\frac{d}{|\mathcal{N}|}}\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}+w\sqrt{c_{2}\frac{d}{|\mathcal{N}|}}\sum_{i\in\mathcal{N}}-\ell^{\prime(t)}_{i}\right]$
$\displaystyle=\lVert\theta^{(t)}\rVert+c_{3}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{i\in[n]}-w_{i}\ell^{\prime(t)}_{i}.$

Therefore, unrolling this bound over $t$ steps we find that

$\displaystyle\lVert\theta^{(t+1)}\rVert$
$\displaystyle\leq\lVert\theta^{(0)}\rVert+c_{3}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}$
(12)
$\displaystyle=c_{3}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}\left[1+\frac{\lVert\theta^{(0)}\rVert}{c_{3}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}\right].$

Thus, combined with inequality (10) we get that,

$\displaystyle\frac{\mu_{1}\cdot\theta^{(t+1)}}{\lVert\theta^{(t+1)}\rVert}$
$\displaystyle\geq\frac{\mu_{1}\cdot\theta^{(0)}}{\lVert\theta^{(t+1)}\rVert}+\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c_{3}\sqrt{d}}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c_{3}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]\times$
$\displaystyle\hskip
72.26999pt\frac{\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c_{1}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right]}{\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}},$

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 $c\geq 1$ such that the following holds
for all large enough $C$, and all small enough step-sizes $\eta$ and for any
$\frac{\tau^{3}}{2}\leq w\leq 2\tau^{3}$. On a good run, for all
$t\in\\{1,2,\ldots\\}$ and all $i\neq j\in[n]$

$\displaystyle\frac{\ell_{i}^{(t)}}{\ell_{j}^{(t)}}\leq
c\left(\frac{w_{j}}{w_{i}}\right)^{1/3}.$

Proof  Let $c_{1}\geq 1$ be the constant $c$ from Lemma B.2 above. We shall
show that the choice $c=\max\left\\{8,2(4c_{1}^{2})^{1/3}\right\\}$ suffices.

We shall prove this via an inductive argument. For the base case, at step
$t=0$, we know that by Lemma B.4 that the ratio between the losses of sample
$i$ and $j$ is upper bounded by $8\left(w_{j}/w_{i}\right)^{1/3}$. Now, we
shall assume that the inductive hypothesis holds at an arbitrary step $t>0$
and prove that it holds at step $t+1$.

Without loss of generality, we shall analyze the ratio between the losses of
the samples with indices $i=1$ and $j=2$. A similar analysis shall hold for
any other pair. Define $G_{t}:=\ell_{1}^{(t)}$, $H_{t}:=\ell_{2}^{(t)}$,
$A_{t}:=H_{t}/G_{t}$. Note that,

$\displaystyle G_{t+1}$ $\displaystyle=\frac{1}{\theta^{(t+1)}\cdot
z_{1}-(\beta-1)}$ $\displaystyle=\frac{1}{\theta^{(t)}\cdot
z_{1}+\eta\sum_{k\in[n]}w_{k}(-\ell^{\prime(t)}_{k})(z_{k}\cdot
z_{1})-(\beta-1)}$ $\displaystyle\overset{(i)}{=}\frac{1}{\theta^{(t)}\cdot
z_{1}-(\beta-1)+\eta\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}}$
$\displaystyle=\frac{\ell^{(t)}_{1}}{1+\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}}$
$\displaystyle=G_{t}\cdot\frac{1}{1+\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}}$

where $(i)$ follows since $-\ell^{\prime(t)}_{k}=(\ell^{(t)}_{k})^{2}$ as the
loss of each example is always in the polynomial tail of the loss by Lemma
B.4. Therefore, we have that

$\displaystyle A_{t+1}=\frac{H_{t+1}}{G_{t+1}}$
$\displaystyle=\frac{H_{t}}{G_{t}}\cdot\frac{1+\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}}{1+\eta\ell^{(t)}_{2}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{2})\left(\ell^{(t)}_{k}\right)^{2}}$
$\displaystyle=A_{t}\cdot\frac{1+\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}}{1+\eta\ell^{(t)}_{2}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{2})\left(\ell^{(t)}_{k}\right)^{2}}.$

Now since the step-size $\eta$ is chosen to be small enough, $|z_{i}\cdot
z_{j}|\leq c_{1}d$ (by Part (3) 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

$\displaystyle 1+\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}$
$\displaystyle\leq\exp\left(\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}\right)$ $\displaystyle
1+\eta\ell^{(t)}_{2}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{2})\left(\ell^{(t)}_{k}\right)^{2}$
$\displaystyle\geq\exp\left(\frac{\eta\ell^{(t)}_{2}}{2}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{2})\left(\ell^{(t)}_{k}\right)^{2}\right),$

and thus,

$\displaystyle A_{t+1}\leq
A_{t}\exp\left(\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}-\frac{\eta\ell^{(t)}_{2}}{2}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{2})\left(\ell^{(t)}_{k}\right)^{2}\right).$ (13)

Let us further upper bound the RHS as follows

$\displaystyle A_{t}\exp\left(\eta\ell^{(t)}_{1}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}-\frac{\eta\ell^{(t)}_{2}}{2}\sum_{k\in[n]}w_{k}(z_{k}\cdot
z_{2})\left(\ell^{(t)}_{k}\right)^{2}\right)$
$\displaystyle=A_{t}\exp\left(\eta w_{1}\left(\ell_{1}^{(t)}\right)^{3}\lVert
z_{1}\rVert^{2}-\frac{1}{2}\eta w_{2}\left(\ell_{2}^{(t)}\right)^{3}\lVert
z_{2}\rVert^{2}\right)$ $\displaystyle\hskip
36.135pt\times\exp\left(\eta\ell^{(t)}_{1}\sum_{k\neq 1}w_{k}(z_{k}\cdot
z_{1})\left(\ell^{(t)}_{k}\right)^{2}-\frac{1}{2}\eta\ell^{(t)}_{2}\sum_{k\neq
2}w_{k}(z_{k}\cdot z_{2})\left(\ell^{(t)}_{k}\right)^{2}\right)$
$\displaystyle\overset{(i)}{\leq}A_{t}\exp\left(c_{1}\eta
dw_{1}\left(\ell_{1}^{(t)}\right)^{3}-\frac{1}{2c_{1}}\eta
dw_{2}\left(\ell_{2}^{(t)}\right)^{3}\right)$ $\displaystyle\hskip
36.135pt\times\exp\left(c_{2}\eta\left(\ell^{(t)}_{1}+\frac{\ell^{(t)}_{2}}{2}\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\ell^{(t)}_{k}\right)^{2}\right)$

where $(i)$ follows since for all $i\in[n]$, $d/c_{1}\leq\lVert
z_{i}\rVert^{2}\leq c_{1}d$ and for any $j\neq k$, $|z_{j}\cdot z_{k}|\leq
c_{1}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)$ by Lemma B.2.
Continuing we get that,

$\displaystyle A_{t+t}$ $\displaystyle\leq A_{t}\exp\left(c_{1}\eta
dw_{1}G_{t}^{3}-\frac{1}{2c_{1}}\eta dw_{2}H_{t}^{3}\right)$
$\displaystyle\hskip
36.135pt\times\exp\left(c_{2}\eta\left(G_{t}+H_{t}\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\ell^{(t)}_{k}\right)^{2}\right)$
$\displaystyle=A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip
14.45377pt\times\exp\left(c_{2}\eta\left(G_{t}+H_{t}\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\ell^{(t)}_{k}\right)^{2}\right),$
(14)

With this upper bound in place, consider two cases.

Case 1 ($A_{t}^{3}\leq\frac{4c_{1}^{2}w_{1}}{w_{2}}$): Using inequality (14)
we know that

$\displaystyle A_{t+1}$ $\displaystyle\leq
A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip
14.45377pt\times\exp\left(c_{2}\eta\left(G_{t}+H_{t}\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\ell^{(t)}_{k}\right)^{2}\right)$
$\displaystyle\leq A_{t}\exp\left(c_{1}\eta
dw_{1}G_{t}^{3}\right)\exp\left(c_{2}\eta\left(G_{t}+H_{t}\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\ell^{(t)}_{k}\right)^{2}\right).$

Now the loss on each example is less than the total initial loss $1/2$ (see
equation (9)) and therefore,

$\displaystyle A_{t+1}$ $\displaystyle\leq A_{t}\exp\left(c_{3}\eta
dw\right)\exp\left(c_{4}\eta\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)wn\right)$
$\displaystyle\overset{(i)}{\leq}\left(\frac{4c_{1}^{2}w_{1}}{w_{2}}\right)^{1/3}\exp(1/8)\leq
2\left(\frac{4c_{1}^{2}w_{1}}{w_{2}}\right)^{1/3}\overset{(ii)}{\leq}c\left(\frac{w_{1}}{w_{2}}\right)^{1/3},$

where $(i)$ follows by choosing the step-size $\eta$ to be small enough and
because $A_{t}\leq\left(\frac{4c_{1}^{2}w_{1}}{w_{2}}\right)^{1/3}$ in this
case, and $(ii)$ follows by the choice of constant $c\geq 2(4c_{1}^{2})^{1/3}$
from above.

Case 2
($\frac{4c_{1}^{2}w_{1}}{w_{2}}<A_{t}^{3}\leq\frac{c^{3}w_{1}}{w_{2}}$): In
this case again by inequality (14)

$\displaystyle A_{t+1}$ $\displaystyle\leq
A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip
14.45377pt\times\exp\left(c_{2}\eta\left(G_{t}+H_{t}\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\ell^{(t)}_{k}\right)^{2}\right)$
$\displaystyle=A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip 14.45377pt\times\exp\left(c_{2}\eta
G_{t}^{3}\left(A_{t}+1\right)\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\frac{\left(\ell^{(t)}_{k}\right)^{2}}{G_{t}^{2}}\right).$

Continuing we find that,

$\displaystyle A_{t+1}$
$\displaystyle\overset{(i)}{\leq}A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip 14.45377pt\times\exp\left(c_{6}\eta
G_{t}^{3}\max\left\\{\left(\frac{w_{1}}{w_{2}}\right)^{1/3},1\right\\}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}w_{k}\left(\frac{w_{1}}{w_{k}}\right)^{2/3}\right)$
$\displaystyle=A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip 14.45377pt\times\exp\left(c_{6}\eta
w_{1}G_{t}^{3}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}\left(\frac{w_{k}}{\min\\{w_{1},w_{2}\\}}\right)^{1/3}\right)$
$\displaystyle\overset{(ii)}{\leq}A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip 14.45377pt\times\exp\left(c_{6}\eta
w_{1}G_{t}^{3}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\left(|\mathcal{P}|+w^{1/3}|\mathcal{N}|\right)\right)$
$\displaystyle=A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)$
$\displaystyle\hskip 14.45377pt\times\exp\left(c_{6}\eta
w_{1}G_{t}^{3}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)|\mathcal{P}|\left(1+\frac{w^{1/3}}{\tau}\right)\right)$
$\displaystyle\overset{(iii)}{\leq}A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\left(A_{t}^{3}-\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\right)\exp\left(2c_{6}\eta
w_{1}G_{t}^{3}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)n\right)$
$\displaystyle\overset{(iv)}{\leq}A_{t}\exp\left(-\frac{1}{2c_{1}}\eta
dw_{2}G_{t}^{3}\cdot\frac{2c_{1}^{2}w_{1}}{w_{2}}\right)\exp\left(2c_{6}\eta
w_{1}G_{t}^{3}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)n\right)$
$\displaystyle=A_{t}\exp\left[-c_{1}w_{1}G_{t}^{3}\left(d-c_{7}n\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\right)\right],$

where $(i)$ follows by the inductive hypothesis which guarantees that
$\frac{\ell_{k}^{(t)}}{\ell_{1}^{(t)}}\leq c(\frac{w_{1}}{w_{k}})^{1/3}\leq
cw^{1/3}$, $(ii)$ follows since $w_{k}=1$ if $k\in\mathcal{P}$ and $w_{k}=w$
if $k\in\mathcal{N}$. Inequality $(iii)$ follows since $w<2\tau^{3}$ and since
$|\mathcal{P}|\leq n$, and finally $(iv)$ follows since in this case
$A_{t}^{3}>\frac{4c_{1}^{2}w_{1}}{w_{2}}$. Now since by assumption the
dimension

$\displaystyle d\geq Cn\lVert\mu\rVert^{2}\geq C^{2}n^{3}\log(n/\delta)$

for a large enough constant $C$. Hence, we have that $A_{t+1}\leq A_{t}\leq
c\left(\frac{w_{1}}{w_{2}}\right)^{1/3}$ in this case.

Recall that since we assumed the inductive hypothesis to 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 at any iteration.

######  Lemma B.7.

For any positive $\tilde{c}$, there exists a $0<c<1$ such that, for all large
enough $C$, if the step-size $\eta$ is sufficiently small and
$\frac{\tau^{3}}{2}\leq w\leq 2\tau^{3}$ then on a good run, for any
$t\in\\{0,1,\ldots\\}$

$\displaystyle\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(t)}_{i}-\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}$
$\displaystyle\geq c\sum_{i\in[n]}-w_{i}\ell^{\prime(t)}_{i}$

and

$\displaystyle\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}-\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(t)}_{i}$
$\displaystyle\geq c\sum_{i\in[n]}-w_{i}\ell^{\prime(t)}_{i}.$

Proof  We begin by proving the first part of the lemma. Note that since
$[n]=\mathcal{P}\cup\mathcal{N}$ to prove the first part it suffices to
instead show that

$\displaystyle(1-c)\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(t)}_{i}\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}$
$\displaystyle\iff(1-c)\sum_{i\in\mathcal{P}}-\ell^{\prime(t)}_{i}\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)w\sum_{i\in\mathcal{N}}-\ell^{\prime(t)}_{i}$
$\displaystyle\iff(1-c)\sum_{i\in\mathcal{P}}(\ell^{(t)}_{i})^{2}\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)w\sum_{i\in\mathcal{N}}(\ell^{(t)}_{i})^{2}$
(since $-\ell^{\prime(t)}_{i}=(\ell_{i}^{(t)})^{2}$ for the polynomial loss)
$\displaystyle\Leftarrow(1-c)|\mathcal{P}|\min_{i\in\mathcal{P}}(\ell^{(t)}_{i})^{2}\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)w|\mathcal{N}|\max_{i\in\mathcal{N}}(\ell^{(t)}_{i})^{2}$
$\displaystyle\Leftarrow(1-c)\tau\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)w\frac{\max_{i\in\mathcal{N}}(\ell^{(t)}_{i})^{2}}{\min_{i\in\mathcal{P}}(\ell^{(t)}_{i})^{2}}$
$\displaystyle\Leftarrow(1-c)\tau\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)wc_{1}\cdot\frac{1}{w^{2/3}}$
(by invoking Lemma B.6; note that $c_{1}\geq 1$)
$\displaystyle\Leftarrow\frac{(1-c)}{c_{1}\left(c+\frac{\tilde{c}}{\sqrt{C}}\right)}\tau\geq
w^{1/3}$ $\displaystyle\hskip 108.405pt\mbox{(since
$\lVert\mu\rVert\geq\sqrt{Cn^{2}\log(n/\delta)}$, where $C$ is a large enough
constant)}.$

Since $C$ is large enough, we now choose the constant $0<c<1$ to be such that
$(1-c)/(c_{1}(c+\tilde{c}/\sqrt{C}))$ is at least $(2)^{1/3}$. This proves the
first part of the lemma.

To prove the second part of the lemma, note that again since
$[n]=\mathcal{P}\cup\mathcal{N}$ it suffices to show that

$\displaystyle(1-c)\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(t)}_{i}\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(t)}_{i}$
$\displaystyle\Leftarrow(1-c)|\mathcal{N}|w\min_{i\in\mathcal{N}}(\ell^{(t)}_{i})^{2}\geq\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)|\mathcal{P}|\max_{i\in\mathcal{P}}(\ell^{(t)}_{i})^{2}$
$\displaystyle\Leftarrow
w\geq\frac{\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)}{(1-c)}\frac{\max_{i\in\mathcal{P}}(\ell^{(t)}_{i})^{2}}{\min_{i\in\mathcal{N}}(\ell^{(t)}_{i})^{2}}\cdot\tau$
$\displaystyle\Leftarrow
w\geq\frac{\left(c+\frac{\tilde{c}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)}{(1-c)}c_{1}w^{2/3}\tau$
$\displaystyle\Leftarrow
w^{1/3}\geq\frac{c_{1}\left(c+\frac{\tilde{c}}{\sqrt{C}}\right)}{(1-c)}\cdot\tau$
$\displaystyle\Leftarrow w^{1/3}\geq\frac{\tau}{2^{1/3}}$

where the last implication follows by the choice of $c$ from above. This
completes the proof.

We now have all the pieces required to prove our main theorem. Recall its
statement. *

Proof  First, by Part (8) of Lemma B.2 we know that the data is linearly
separable. Thus, by Proposition 4.1 we know that

$\displaystyle\widehat{\theta}_{1}=\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}.$

Given this equivalence, by Lemma B.1 we know that

$\displaystyle\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}\left(\widehat{\theta}_{1}\cdot
x\right)\neq y\right]$ $\displaystyle\hskip
36.135pt=\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}\left(\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)\rVert}}\cdot
x\right)\neq y\right]$ $\displaystyle\hskip
36.135pt\leq\frac{1}{2}\left[\exp\left(-c^{\prime}\left(\lim_{t\to\infty}\frac{\theta^{(t)}\cdot\mu_{1}}{\lVert\theta^{(t)}\rVert}\right)^{2}\right)+\exp\left(-c^{\prime}\left(\lim_{t\to\infty}\frac{\theta^{(t)}\cdot\mu_{2}}{\lVert\theta^{(t)}\rVert}\right)^{2}\right)\right].$
(15)

We shall now establish lower bounds on
$\lim_{t\to\infty}\frac{\theta^{(t)}\cdot\mu_{1}}{\lVert\theta^{(t)}\rVert}$
and
$\lim_{t\to\infty}\frac{\theta^{(t)}\cdot\mu_{2}}{\lVert\theta^{(t)}\rVert}$
to obtain the desired bound on the test error. Let us lower bound
$\lim_{t\to\infty}\frac{\theta^{(t)}\cdot\mu_{1}}{\lVert\theta^{(t)}\rVert}$.
The bound on
$\lim_{t\to\infty}\frac{\theta^{(t)}\cdot\mu_{2}}{\lVert\theta^{(t)}\rVert}$
shall follow by exactly the same logic.

By Lemma B.5 we know that

$\displaystyle\lim_{t\to\infty}\frac{\mu_{1}\cdot\theta^{(t+1)}}{\lVert\theta^{(t+1)}\rVert}$
$\displaystyle\geq\lim_{t\to\infty}\frac{\mu_{1}\cdot\theta^{(0)}}{\lVert\theta^{(t+1)}\rVert}+\lim_{t\to\infty}\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c_{1}\sqrt{d}}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]\times$
$\displaystyle\hskip
108.405pt\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c_{2}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right]$
$\displaystyle\overset{(i)}{\geq}\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c_{1}\sqrt{d}}\cdot\lim_{t\to\infty}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]\times$
$\displaystyle\hskip
108.405pt\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c_{2}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right]$
$\displaystyle=\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c_{1}\sqrt{d}}\cdot\lim_{t\to\infty}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]\times$
$\displaystyle\hskip
108.405pt\lim_{t\to\infty}\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c_{2}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right],$
(16)

where $(i)$ follows since $\mu_{1}\cdot\theta^{(0)}$ is bounded and
$\lVert\theta^{(t+1)}\rVert\to\infty$ by [Ji+20].

We will now show that the first limit in RHS equals $1$. To do this, first
note that

$\displaystyle
1\geq\lim_{t\to\infty}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]$
$\displaystyle=\left[\frac{1}{1+\lim_{t\to\infty}\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right].$

Now we will show that

$\displaystyle\lim_{t\to\infty}\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}=0.$

First note that
$\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{d}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}\geq
0$, since $-w_{i}\ell^{\prime(s)}_{i}\geq 0$, so to show that this limit
equals $0$, it suffices to show that
$c_{1}\eta\sqrt{d}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}$
grows unboundedly as $t\to\infty$. Using inequality (12) from above we get
that,

$\displaystyle\lVert\theta^{(t+1)}\rVert$
$\displaystyle\leq\lVert\theta^{(0)}\rVert+c_{3}\eta\sqrt{\frac{d}{|\mathcal{N}|}}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}.$

The norm $\lVert\theta^{(0)}\rVert$ is finite and we know that
$\lVert\theta^{(t)}\rVert\to\infty$ by [Ji+20], therefore
$c_{1}\eta\sqrt{d}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}$ must
grow unboundedly. This proves that

$\displaystyle\lim_{t\to\infty}\left[\frac{1}{1+\frac{\lVert\theta^{(0)}\rVert}{c_{1}\eta\sqrt{d}\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}}\right]=1$

as claimed. This combined with inequality (16) yields the bound

$\displaystyle\lim_{t\to\infty}\frac{\mu_{1}\cdot\theta^{(t+1)}}{\lVert\theta^{(t+1)}\rVert}$
$\displaystyle\geq\frac{\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{2c_{1}\sqrt{d}}\lim_{t\to\infty}\frac{\sum_{s=0}^{t}\left[\sum_{i\in\mathcal{P}}-w_{i}\ell^{\prime(s)}_{i}-\frac{c_{2}\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\sum_{i\in\mathcal{N}}-w_{i}\ell^{\prime(s)}_{i}\right]}{\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}$
$\displaystyle\overset{(i)}{\geq}\frac{c_{3}\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{\sqrt{d}}\lim_{t\to\infty}\frac{\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}{\sum_{s=0}^{t}\sum_{i\in[n]}-w_{i}\ell^{\prime(s)}_{i}}$
$\displaystyle=\frac{c_{3}\lVert\mu\rVert^{2}\sqrt{|\mathcal{N}|}}{\sqrt{d}}$
$\displaystyle=\frac{c_{3}\lVert\mu\rVert^{2}\sqrt{|\mathcal{P}|}}{\sqrt{\tau
d}}$
$\displaystyle\overset{(ii)}{\geq}\frac{c_{4}\lVert\mu\rVert^{2}\sqrt{n}}{\sqrt{\tau
d}}$

where $(i)$ follows by invoking Lemma B.7 and $(ii)$ follows since
$|\mathcal{P}|\geq n/2$. As stated above, using a similar argument we can also
show that
$\lim_{t\to\infty}\frac{\mu_{1}\cdot\theta^{(t+1)}}{\lVert\theta^{(t+1)}\rVert}\geq\frac{c_{4}\lVert\mu\rVert^{2}\sqrt{n}}{\sqrt{\tau
d}}$. Plugging these lower bounds into inequality (15) completes our proof.

##  Appendix C Proof of Theorem 4.2.3

In this section we will prove a lower bound on the test error of the maximum
margin linear classifier $\widehat{\theta}_{\mathsf{MM}}$. Here we will work
with the exponential loss

$\displaystyle\ell(z)=\exp(-z).$

Define the loss
$\widehat{L}(\theta)=\sum_{i\in[n]}\ell(y_{i}x_{i}^{\top}\theta)=\sum_{i\in[n]}\ell(z_{i}^{\top}\theta)$.
For a step-size $\eta$ and initial iterate $\theta^{(0)}=0$ (this choice of
initial point is for the sake of convenience, it does not affect the implicit
bias of gradient descent) for any $t\in\\{0,1,\ldots\\}$

$\displaystyle\theta^{(t+1)}$
$\displaystyle=\theta^{(t)}-\eta\nabla\widehat{L}(\theta^{(t)})$

be the iterates of gradient descent. We let $\ell_{i}^{(t)}$ be shorthand for
$\ell(z_{i}\cdot\theta^{(t)})$ and therefore,

$\displaystyle\theta^{(t+1)}=\theta^{(t)}-\eta\nabla\widehat{L}(\theta^{(t)})=\theta^{(t)}+\eta\sum_{i\in[n]}z_{i}\ell_{i}^{(t)}.$

The results by [Sou+18] guarantee that for a small enough step-size $\eta$ the
direction of the iterates of gradient descent
$\lim_{t\to\infty}\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}=\widehat{\theta}_{\mathsf{MM}}$.
Therefore, we will instead prove a lower bound on the asymptotic iterates of
gradient descent.

As we did in the proof of Theorem 4.2.2, going forward we will assume that a
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
$\mathcal{S}$.

With the setup in place, we shall now prove this theorem in stages. Throughout
this section the assumptions stated in Section 4.2.1 shall remain in force. We
begin with a lemma that shows that the margin of the maximum margin classifier
scales with $\sqrt{d/n}$.

######  Lemma C.1.

There is an absolute constant $c$ such that, on a good run, for all large
enough $C$, for all $i\in[n]$

$\displaystyle\widehat{\theta}_{\mathsf{MM}}\cdot z_{i}\geq
c\sqrt{\frac{d}{n}}.$

Proof  We will prove this result by constructing a unit vector $\phi$ with a
margin that scales with $\sqrt{d/n}$. This immediately implies that the
maximum margin classifier must also attain this margin on all of the points.

Define $\phi$ to be as follows

$\displaystyle\phi$
$\displaystyle:=\frac{\sum_{i\in[n]}z_{i}}{\lVert\sum_{j\in[n]}z_{j}\rVert}.$

We will first bound the norm of the denominator as follows

$\displaystyle\left\lVert\sum_{j\in[n]}z_{j}\right\rVert^{2}$
$\displaystyle=\sum_{j\in[n]}\lVert z_{j}\rVert^{2}+\sum_{j\neq k}z_{j}\cdot
z_{k}$ $\displaystyle\leq\sum_{j\in[n]}\lVert z_{j}\rVert^{2}+\sum_{j\neq
k}|z_{j}\cdot z_{k}|$
$\displaystyle\overset{(i)}{\leq}c_{1}nd+c_{1}n^{2}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)$
$\displaystyle=c_{1}nd\left(1+\frac{c_{1}\lVert\mu\rVert^{2}}{d}+\frac{n\sqrt{\log(n/\delta)}}{\sqrt{d}}\right)$
$\displaystyle\overset{(ii)}{\leq}2c_{1}nd$ (17)

where $(i)$ follows by Lemma B.2 and $(ii)$ follows since $d\geq
Cn\lVert\mu\rVert^{2}\geq C^{2}n^{3}\log(n/\delta)$ where recall $C$ is
sufficiently large.

Now we lower bound the margin between numerator of $v$ and $z_{k}$ for any
$k\in[n]$

$\displaystyle\left(\sum_{i\in[n]}z_{i}\right)\cdot z_{k}=\lVert
z_{i}\rVert^{2}+\sum_{i\neq k}z_{i}\cdot z_{k}$ $\displaystyle\geq\lVert
z_{i}\rVert^{2}-\sum_{k\neq i}|z_{i}\cdot z_{k}|$
$\displaystyle\overset{(i)}{\geq}\frac{d}{c_{1}}-c_{1}n(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)})$
$\displaystyle=\frac{d}{c_{1}}\left(1-\frac{c_{1}^{2}n\lVert\mu\rVert^{2}}{d}-\frac{c_{1}^{2}n\sqrt{\log(n/\delta)}}{\sqrt{d}}\right)$
$\displaystyle\geq\frac{d}{2c_{1}},$ (18)

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\in[n]$

$\displaystyle\phi\cdot z_{k}$
$\displaystyle\geq\frac{d}{2c_{1}\sqrt{2c_{1}nd}}=c\sqrt{\frac{d}{n}}.$

This proves the result.

The next lemma provides control over the rate at which the norm of iterates
$\theta^{(t)}$ grows late in training.

######  Lemma C.2.

There is an absolute constant $c$ such that, for all large enough $C$, if the
step-size $\eta$ is sufficiently small then on a good run, there exists a
$t_{0}$ such that for all $t\geq t_{0}$

$\displaystyle\lVert\theta^{(t+1)}\rVert$
$\displaystyle\geq\lVert\theta^{(t)}\rVert+c\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}.$

Proof By the definition of gradient descent

$\displaystyle\lVert\theta^{(t+1)}\rVert^{2}$
$\displaystyle=\lVert\theta^{(t)}+\eta\sum_{i\in[n]}\ell_{i}^{(t)}z_{i}\rVert^{2}$
$\displaystyle=\lVert\theta^{(t)}\rVert^{2}+2\eta\sum_{k\in[n]}\ell_{i}^{(t)}z_{i}\cdot\theta^{(t)}+\eta^{2}\lVert\sum_{i\in[n]}\ell_{i}^{(t)}z_{i}\rVert^{2}$
$\displaystyle\geq\lVert\theta^{(t)}\rVert^{2}+2\eta\sum_{i\in[n]}\ell_{i}^{(t)}z_{i}\cdot\theta^{(t)}.$
(19)

Now we know that
$\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}\to\widehat{\theta}_{\mathsf{MM}}$.
Also note that in the previous lemma (Lemma C.1) we showed that for all
$i\in[n]$

$\displaystyle\widehat{\theta}_{\mathsf{MM}}\cdot z_{i}\geq
c_{1}\sqrt{\frac{d}{n}}.$

Therefore, there exists a iteration $t_{1}$ such that for all $t\geq t_{1}$
and all $i\in[n]$

$\displaystyle\frac{\theta^{(t)}\cdot
z_{i}}{\lVert\theta^{(t)}\rVert}\geq\frac{c_{1}}{2}\sqrt{\frac{d}{n}}.$

Continuing from (19), for any $t\geq t_{1}$

$\displaystyle\lVert\theta^{(t+1)}\rVert^{2}$
$\displaystyle\geq\lVert\theta^{(t)}\rVert^{2}+2\eta\sum_{i\in[n]}\ell_{i}^{(t)}z_{i}\cdot\theta^{(t)}$
$\displaystyle\geq\lVert\theta^{(t)}\rVert^{2}+c_{1}\eta\lVert\theta^{(t)}\rVert\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}$
$\displaystyle=\lVert\theta^{(t)}\rVert^{2}\left[1+\frac{c_{1}\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}}{\lVert\theta^{(t)}\rVert}\right].$

Taking square roots we get that for any $t\geq t_{1}$

$\displaystyle\lVert\theta^{(t+1)}\rVert\geq\lVert\theta^{(t)}\rVert\sqrt{1+\frac{c_{1}\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}}{\lVert\theta^{(t)}\rVert}}.$
(20)

Further by [Ji+20] we know that $\lVert\theta^{(t)}\rVert\rightarrow\infty$,
so there exists a $t_{2}$ such that for all $t\geq t_{2}$,
$\lVert\theta^{(t)}\rVert\geq\frac{c_{1}\eta\sqrt{nd}}{8}$. Thus, for $t\geq
t_{2}$, we have

$\displaystyle\frac{1}{\lVert\theta^{(t)}\rVert}\cdot
c_{1}\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}\leq
8\cdot\frac{\sum_{i\in[n]}\ell_{i}^{(t)}}{n}\leq 8,$ (21)

where the last inequality follows since the initial loss is equal to $n$, as
$\theta^{(0)}=0$, and the total loss is decreasing again by [Ji+20] if the
step-size is small enough. It is easy to check that for any $0\leq x\leq 8$

$\displaystyle\sqrt{1+x}\geq 1+\frac{x}{4}.$

Thus, combining inequalities (20) and (21) we get that for all $t\geq
t_{0}=\max\\{t_{1},t_{2}\\}$

$\displaystyle\lVert\theta^{(t+1)}\rVert\geq\lVert\theta^{(t)}\rVert\sqrt{1+\frac{c_{1}\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}}{\lVert\theta^{(t)}\rVert}}$
$\displaystyle\geq\lVert\theta^{(t)}\rVert\left(1+\frac{c_{1}\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)}}{4\lVert\theta^{(t)}\rVert}\right)$
$\displaystyle=\lVert\theta^{(t)}\rVert+\frac{c_{1}}{4}\eta\sqrt{\frac{d}{n}}\sum_{i\in[n]}\ell_{i}^{(t)},$

which completes our proof.
Continuing we will show that throughout training the ratio of the losses
between the different examples are bounded by a 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 $\mu_{1}$ than the mean of the minority
negative center $\mu_{2}$.

The proof is identical to the proof of Lemma 11 by [CL21]. 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 $c$ such that, for all large enough $C$, and all
small enough step sizes $\eta$, on a good run, for all iterations
$t\in\\{0,1,\ldots\\}$ and all $i,j\in[n]$

$\displaystyle\frac{\ell_{i}^{(t)}}{\ell_{j}^{(t)}}\leq c.$

Proof  First note that
$\widehat{L}(\theta^{(0)})=\sum_{i\in[n]}\ell_{i}^{(0)}=n$ and since step-size
$\eta$ is small enough training loss is non-increasing by [Ji+20].

Let $c_{1}$ be the constant $c\geq 1$ from Lemma B.2. We will show that
$c=4c_{1}^{2}$ suffices.

We shall prove this via an inductive argument. For the base case, at step
$t=0$, we know that $\theta^{(0)}=0$, therefore the loss on all of the samples
is equal to $1$. Now, we shall assume that the inductive hypothesis holds at
an arbitrary step $t>0$ and prove that it holds at step $t+1$.

Without loss of generality, we shall analyze the ratio between the losses of
the samples with indices $i=1$ and $j=2$. A similar analysis shall hold for
any other pair. Define $G_{t}:=\ell_{1}^{(t)}$, $H_{t}:=\ell_{2}^{(t)}$,
$A_{t}:=H_{t}/G_{t}$. The ratio between these losses at step $t+1$ is

$\displaystyle A_{t+1}$ $\displaystyle=\frac{\exp(-\theta^{(t+1)}\cdot
z_{2})}{\exp(-\theta^{(t+1)}\cdot z_{1})}$
$\displaystyle=\frac{\exp(-(\theta^{(t)}+\eta\sum_{k\in[n]}\ell_{k}^{(t)}z_{k})\cdot
z_{2})}{\exp(-(\theta^{(t)}+\eta\sum_{k\in[n]}\ell_{k}^{(t)}z_{k})\cdot
z_{1})}$
$\displaystyle=A_{t}\cdot\exp\left(-\eta\sum_{k\in[n]}\ell_{k}^{(t)}\left(z_{k}\cdot
z_{2}-z_{k}\cdot z_{1}\right)\right)$
$\displaystyle=A_{t}\cdot\exp\left(-\eta\left(\ell_{2}^{(t)}\lVert
z_{2}\rVert^{2}-\ell_{1}^{(t)}\lVert z_{1}\rVert^{2}-\sum_{k\neq
2}\ell_{k}^{(t)}z_{k}\cdot z_{2}+\sum_{k\neq 1}\ell_{k}^{(t)}z_{k}\cdot
z_{1}\right)\right)$ $\displaystyle=A_{t}\cdot\exp\left(-\eta\left(H_{t}\lVert
z_{2}\rVert^{2}-G_{t}\lVert z_{1}\rVert^{2}-\sum_{k\neq
2}\ell_{k}^{(t)}z_{k}\cdot z_{2}+\sum_{k\neq 1}\ell_{k}^{(t)}z_{k}\cdot
z_{1}\right)\right)$ $\displaystyle\leq
A_{t}\cdot\exp\left(-\eta\left(H_{t}\lVert z_{2}\rVert^{2}-G_{t}\lVert
z_{1}\rVert^{2}-\sum_{k\neq 2}\ell_{k}^{(t)}|z_{k}\cdot z_{2}|-\sum_{k\neq
1}\ell_{k}^{(t)}|z_{k}\cdot z_{1}|\right)\right).$

Now note that by Lemma B.2, for all $i\neq j\in[n]$, $d/c_{1}\leq\lVert
z_{i}\rVert^{2}\leq c_{1}d$ and $|z_{i}\cdot z_{j}|\leq
c_{1}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)$, and therefore,

$\displaystyle A_{t+1}$ $\displaystyle\leq
A_{t}\cdot\exp\left(-\eta\left(\frac{H_{t}d}{c_{1}}-G_{t}c_{1}d-2c_{1}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)\sum_{k\in[n]}\ell_{k}^{(t)}\right)\right)$
$\displaystyle=A_{t}\cdot\exp\left(-\eta\left(\frac{G_{t}d}{c_{1}}\left(A_{t}-c_{1}^{2}\right)-2c_{1}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)G_{t}\sum_{k\in[n]}\frac{\ell_{k}^{(t)}}{G_{t}}\right)\right)$
$\displaystyle\overset{(i)}{\leq}A_{t}\cdot\exp\left(-\eta\left(\frac{G_{t}d}{c_{1}}\left(A_{t}-c_{1}^{2}\right)-8c_{1}^{3}\left(\lVert\mu\rVert^{2}+\sqrt{d\log(n/\delta)}\right)G_{t}n\right)\right)$
$\displaystyle=A_{t}\cdot\exp\left(-\frac{\eta
G_{t}d}{c_{1}}\left(A_{t}-c_{1}^{2}-8c_{1}^{4}\left(\frac{\lVert\mu\rVert^{2}n}{d}+\frac{n\sqrt{\log(n/\delta)}}{\sqrt{d}}\right)\right)\right)$
$\displaystyle\overset{(ii)}{\leq}A_{t}\cdot\exp\left(-\frac{\eta
G_{t}d}{c_{1}}\left(A_{t}-c_{1}^{2}-8c_{1}^{4}\left(\frac{1}{C}+\frac{1}{C}\right)\right)\right)$
$\displaystyle\overset{(iii)}{\leq}A_{t}\cdot\exp\left(-\frac{\eta
G_{t}d}{c_{1}}\left(A_{t}-2c_{1}^{2}\right)\right),$ (22)

where $(i)$ follows since by the inductive hypothesis
$\ell_{k}^{(t)}/G_{t}\leq c=4c_{1}^{2}$, $(ii)$ follows since by assumption
$d\geq Cn\lVert\mu\rVert^{2}\geq C^{2}n^{3}\log(n/\delta)$, and $(iii)$
follows since $C$ is sufficiently large.

Now consider two cases.

Case 1 ($A_{t}\leq 2c_{1}^{2}$):  By inequality (22)

$\displaystyle A_{t+1}\leq A_{t}\cdot\exp\left(-\frac{\eta
G_{t}d}{c_{1}}\left(A_{t}-2c_{1}^{2}\right)\right)=A_{t}\exp\left(\frac{\eta
G_{t}d}{c_{1}}\left(2c_{1}^{2}-A_{t}\right)\right)$ $\displaystyle\leq
2c_{1}^{2}\exp\left(2\eta c_{1}G_{t}d\right)$ $\displaystyle\leq
2c_{1}^{2}\exp\left(2\eta c_{1}nd\right)$ $\displaystyle\leq 4c_{1}^{2},$

where the last inequality follows if the step-size $\eta$ is sufficiently
small.

Case 2 ($2c_{1}^{2}\leq A_{t}\leq 4c_{1}^{2}=c$):  Again by inequality (22)

$\displaystyle A_{t+1}$ $\displaystyle\leq A_{t}\cdot\exp\left(-\frac{\eta
G_{t}d}{c_{1}}\left(A_{t}-2c_{1}^{2}\right)\right)\leq A_{t}\leq 4c_{1}^{2}.$

Thus, we have shown that $A_{t+1}\leq 4c_{1}^{2}=c$ in both cases. Since we
assumed the induction hypothesis to hold at step $t$, 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 $\theta^{(t+1)}\cdot\mu_{2}$ and the corresponding inner
product at iteration $t$. Since we start at $\theta^{(0)}$, unrolling this
over $t$ steps gives us an upper bound on inner product
$\theta^{(t)}\cdot\mu_{2}$ for any $t\geq 0$.

######  Lemma C.4.

There is an absolute constant $c$ such that, for all large enough $C$, if the
step-size $\eta$ is sufficiently small then on a good run, for all
$t\in\\{0,1,\ldots\\}$

$\displaystyle\left(\theta^{(t+1)}-\theta^{(t)}\right)\cdot(-\mu_{2})\leq\frac{c\eta\lVert\mu\rVert^{2}}{\tau}\sum_{i\in[n]}\ell_{i}^{(t)}.$

Proof By the definition of a gradient descent step

$\displaystyle(\theta^{(t+1)}-\theta^{(t)})\cdot(-\mu_{2})$
$\displaystyle=\eta\sum_{i\in[n]}\ell_{i}^{(t)}z_{i}\cdot(-\mu_{2})$
$\displaystyle\overset{(i)}{\leq}\frac{3\eta\lVert\mu\rVert^{2}}{2}\sum_{i\in\mathcal{N}}\ell_{i}^{(t)}+c_{1}\eta\lVert\mu\rVert\sqrt{\log(n/\delta)}\sum_{i\in\mathcal{P}}\ell_{i}^{(t)}$
$\displaystyle\overset{(ii)}{\leq}\frac{3\eta\lVert\mu\rVert^{2}}{2}\cdot\frac{c_{2}|\mathcal{N}|}{n}\sum_{i\in[n]}\ell_{i}^{(t)}+c_{1}\eta\lVert\mu\rVert\sqrt{\log(n/\delta)}\cdot\frac{c_{2}|\mathcal{P}|}{n}\sum_{i\in[n]}\ell_{i}^{(t)}$
$\displaystyle=\frac{3c_{2}\eta\lVert\mu\rVert^{2}}{2}\cdot\frac{|\mathcal{P}|}{n}\left(\frac{|\mathcal{N}|}{|\mathcal{P}|}+\frac{\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right)\sum_{i\in[n]}\ell_{i}^{(t)}$
$\displaystyle\leq
3c_{2}\eta\lVert\mu\rVert^{2}\max\left\\{\frac{|\mathcal{N}|}{|\mathcal{P}|},\frac{\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right\\}\sum_{i\in[n]}\ell_{i}^{(t)},$

where $(i)$ follows by Lemma B.2 and $(ii)$ follows by the loss ratio bound in
Lemma C.3. Since by assumption $\lVert\mu\rVert^{2}\geq Cn^{2}\log(n/\delta)$,
we infer that

$\displaystyle\frac{\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}$
$\displaystyle\leq\frac{1}{n}\leq\frac{|\mathcal{N}|}{|\mathcal{P}|}=\frac{1}{\tau}.$

Thus,

$\displaystyle(\theta^{(t+1)}-\theta^{(t)})\cdot(-\mu_{2})$ $\displaystyle\leq
3c_{2}\eta\lVert\mu\rVert^{2}\max\left\\{\frac{|\mathcal{N}|}{|\mathcal{P}|},\frac{\sqrt{\log(n/\delta)}}{\lVert\mu\rVert}\right\\}\sum_{i\in[n]}\ell_{i}^{(t)}=\frac{c\eta\lVert\mu\rVert^{2}}{\tau}\sum_{i\in[n]}\ell_{i}^{(t)},$

wrapping up our proof.

With these lemmas in place we are now ready to prove our result. Let us
restate it here. *

Proof  The test error for $\widehat{\theta}_{\mathsf{MM}}$ is

$\displaystyle\mathsf{TestError}[\widehat{\theta}_{\mathsf{MM}}]$
$\displaystyle\quad=\mathbb{P}_{(x,y)\sim\mathsf{P}_{\mathsf{test}}}\left[\mathrm{sign}\left(\widehat{\theta}_{\mathsf{MM}}\cdot
x\right)\neq y\right]$
$\displaystyle\quad=\frac{1}{2}\mathbb{P}_{q\sim\mathsf{N}(0,\frac{1}{2}I_{p\times
p})}\left[\mathrm{sign}\left(\widehat{\theta}_{\mathsf{MM}}\cdot(\mu_{1}+q)\right)\neq
1\right]+\frac{1}{2}\mathbb{P}_{q\sim\mathsf{N}(0,\frac{1}{2}I_{p\times
p})}\left[\mathrm{sign}\left(\widehat{\theta}_{\mathsf{MM}}\cdot(\mu_{2}+q)\right)\neq-1\right]$
$\displaystyle\quad\geq\frac{1}{2}\mathbb{P}_{q\sim\mathsf{N}(0,\frac{1}{2}I_{p\times
p})}\left[\mathrm{sign}\left(\widehat{\theta}_{\mathsf{MM}}\cdot(\mu_{2}+q)\right)\neq-1\right]$
$\displaystyle\quad=\frac{1}{2}\mathbb{P}_{q\sim\mathsf{N}(0,\frac{1}{2}I_{p\times
p})}\left[-\widehat{\theta}_{\mathsf{MM}}\cdot\mu_{2}-\widehat{\theta}_{\mathsf{MM}}\cdot
q<0\right]$
$\displaystyle\quad=\frac{1}{2}\mathbb{P}_{q\sim\mathsf{N}(0,\frac{1}{2}I_{p\times
p})}\left[-\widehat{\theta}_{\mathsf{MM}}\cdot
q<-\widehat{\theta}_{\mathsf{MM}}\cdot(-\mu_{2})\right]$
$\displaystyle\quad=\frac{1}{2}\mathbb{P}_{\xi\sim\mathsf{N}(0,1)}\left[\xi<-\widehat{\theta}_{\mathsf{MM}}\cdot(-\mu_{2})\right]\hskip
14.45377pt\mbox{(since $-\widehat{\theta}_{\mathsf{MM}}\cdot
q\sim\mathsf{N}(0,1)$)}$
$\displaystyle\quad=\frac{\Phi(-\widehat{\theta}_{\mathsf{MM}}\cdot(-\mu_{2}))}{2},$
(23)

where $\Phi$ is the Gaussian cumulative distribution function.

With this inequality in place, we want to prove an upper bound on
$\left(\widehat{\theta}_{\mathsf{MM}}\cdot(-\mu_{2})\right)^{2}$. Now, since
$\frac{\theta^{(t)}}{\lVert\theta^{(t)}\rVert}\to\widehat{\theta}_{\mathsf{MM}}$,
it suffices to prove an upper bound on
$\left(\lim_{t\to\infty}\frac{\theta^{(t)}\cdot(-\mu_{2})}{\lVert\theta^{(t)}\rVert}\right)^{2}$
instead.

To do this, going forward let us assume that a good run (see Definition B.3)
occurs. Lemma B.2 guarantees that this happens with probability at least
$1-\delta$.

Let $t_{0}$ be the constant from Lemma C.2, then by Lemma C.4 we have that for
any $t>t_{0}$

$\displaystyle\theta^{(t)}\cdot(-\mu_{2})$
$\displaystyle=\theta^{(0)}\cdot(-\mu_{2})+\sum_{s=1}^{t_{0}}(\theta^{(s)}-\theta^{(s-1)})\cdot(-\mu_{2})+\sum_{s=t_{0}+1}^{t}\left(\theta^{(s)}-\theta^{(s-1)}\right)\cdot(-\mu_{2})$
$\displaystyle\leq\psi+\frac{c_{1}\eta\lVert\mu\rVert^{2}}{\tau}\sum_{s=t_{0}}^{t-1}\sum_{i\in[n]}\ell_{i}^{(s)},$
(24)

where we define
$\psi:=\theta^{(0)}\cdot(-\mu_{2})+\sum_{s=1}^{t_{0}}\left(\theta^{(s)}-\theta^{(s-1)}\right)\cdot(-\mu_{2})$.

On the other hand, by repeatedly applying Lemma C.2 we get that

$\displaystyle\lVert\theta^{(t)}\rVert$
$\displaystyle\geq\lVert\theta^{(t_{0})}\rVert+c_{2}\eta\sqrt{\frac{d}{n}}\sum_{s=t_{0}}^{t-1}\sum_{i\in[n]}\ell_{i}^{(s)}.$
(25)

Furthermore, since $\lVert\theta^{(t)}\rVert\rightarrow\infty$ [Ji+20, by] and

$\displaystyle\lVert\theta^{(t+1)}\rVert=\left\lVert\theta^{(0)}+\eta\sum_{s=0}^{t}\sum_{i\in[n]}\ell_{i}^{(s)}z_{i}\right\rVert$
$\displaystyle\leq\eta\sum_{s=0}^{t}\sum_{i\in[n]}\ell_{i}^{(s)}\lVert
z_{i}\rVert$ $\displaystyle\leq c_{3}\eta
d\sum_{s=0}^{t}\sum_{i\in[n]}\ell_{i}^{(s)}\hskip 28.90755pt\mbox{(by
Part\leavevmode\nobreak\ \ref{event:1} of Lemma\leavevmode\nobreak\
\ref{lem:normbounds})}$ $\displaystyle=c_{3}\eta
d\sum_{s=0}^{t_{0}-1}\sum_{i\in[n]}\ell_{i}^{(s)}+c_{3}\eta
d\sum_{s=t_{0}}^{t}\sum_{i\in[n]}\ell_{i}^{(s)}$

we can conclude that
$\sum_{s=t_{0}}^{t}\sum_{i\in[n]}\ell_{i}^{(s)}\rightarrow\infty$.

Thus combining inequalities (24) and (25) we get that

$\displaystyle\lim_{t\rightarrow\infty}\frac{\theta^{(t)}\cdot(-\mu_{2})}{\lVert\theta^{(t)}\rVert}$
$\displaystyle\leq\lim_{t\rightarrow\infty}\frac{\psi+\frac{c_{1}\eta\lVert\mu\rVert^{2}}{\tau}\sum_{s=t_{0}}^{t-1}\sum_{i\in[n]}\ell_{i}^{(s)}}{\lVert\theta^{(t_{0})}\rVert+c_{2}\eta\sqrt{\frac{d}{n}}\sum_{s=t_{0}}^{t-1}\sum_{i\in[n]}\ell_{i}^{(s)}}=\frac{c_{4}}{\tau}\sqrt{\frac{n}{d}}\lVert\mu\rVert^{2}.$

Plugging this upper bound into inequality (23) completes the proof.

##  Appendix D Experimental details

###  D.1 Hyperparameters

####  D.1.1 For Section 5.1

##### Imbalanced binary CIFAR10 experiments.

We use the same convolutional neural network architecture with random
initialization as [BL19]. 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 ($\overline{w}$)”, and “IW-ES ($\overline{w}$)”. We use a constant 0.008
learning rate with no momentum for “IW ($\overline{w}^{3/2}$)”, and “IW-ES
($\overline{w}^{3/2}$)”.

##### Subsampled CelebA experiments.

We use a ResNet50 architecture with ImageNet initialization as done in
[Sag+19]. 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 a batch size of 64. We chose
hyperparameters that resulted in stable training for each setting. We use a
constant 0.0004 learning rate with 0.9 momentum for all settings.

####  D.1.2 For Section 5.2

To fairly evaluate every method, we grid search the hyperparamters for each
method extensively. We kept the same architectural setup as 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 on the full dataset and average results over random undersamplings
plus initializations

  * •

LDAM: Following the original paper [Cao+19], we grid search the margin
hyperparameter 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 [Kin+21], we tune $\tau$ and $\gamma$
with $\tau=0$ being CDT loss and $\gamma=0$ being LA Loss. We grid search
across
$(\tau,\gamma)\in[0.0,0.5,1.0,1.5,2.0,2.5,3.0]\times[0.0,0.1,0.2,0.3,0.4,0.5]$.
We found $\tau=3$ to be the best for LA loss, $\gamma=0.5$ to be the best for
CDT loss, and $\tau=3,\gamma=0.3$ to be the best for VS Loss. Unlike the
original paper [Kin+21], we found that the best hyperparameters of VS loss are
similar to those of LA Loss. We initially followed the recommendations of
[Kin+21] and grid searched over
$(\tau,\gamma)\in[0.5,0.75,1.0,1.25,1.5]\times[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 $\tau=1,\gamma=0.05$). Hence, we did a more extensive tuning
afterwards.

  * •

Poly-tailed Loss: We grid search over
$(\alpha,c)\in[0.25,0.5,1.0,2.0,4.0]\times[1.0,1.5,2.0,2.5,3.0]$. We found
$\alpha=2$ and exponent $c=3$ to 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 in [Kin+21] for group-sensitive VS
Loss and grid search over $\gamma\in[0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]$. We
found $\gamma=0.4$ to be the best.

  * •

Poly Loss: We grid search over
$(\alpha,c)\in[1,2,3]\times[1.0,1.5,2.0,2.5,3.0]$. We found $\alpha=2$ and
exponent $c=2.5$ to be the best.

  * •

Cross entropy + DRO: We tune the adversarial step size $\eta_{q}$ over
$[0.0025,0.005,0.01,0.02,0.03,0.04,0.05,0.1]$. We found $\eta_{q}=0.05$ to be
the best.

  * •

VS Loss + DRO: We used the best $\gamma$ from VS Loss alone and
$\eta_{q}=0.05$ for DRO.

  * •

Poly Loss + DRO: We used the best $\alpha$ from Poly Loss alone and
$\eta_{q}=0.05$ for DRO.

###  D.2 Importance weight computation.

Here we explain in greater detail how we compute the importance weights. Note
that the scale of 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 CIFAR10 and $G=4$ for CelebA. Let
$n_{1},\ldots,n_{G}$ be the counts of each group in the training set. Let $n$
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. 1.

For each example $i$ that belongs to group $g$, compute the unbiased weight:
$\overline{w}_{i}\leftarrow 1/n_{g}$.

  2. 2.

Exponentiate the weights by $c$ if necessary:
$w_{i}\leftarrow\overline{w}_{i}^{c}$. No importance weighting corresponds to
$c=0$. Unbiased importance weighting corresponds to $c=1$.

  3. 3.

To adjust for the scale of weights, normalize by the average exponentiated
weight across the _full_ training set: $w_{i}\leftarrow
w_{i}/\sum_{j=1}^{n}w_{i}$. Only normalizing across each minibatch can result
in unstable training, especially when a minibatch contains no representatives
from a group.

###  D.3 Early-stopping metric.

We use the checkpoint with the highest importance weighted validation accuracy
when early stopping. 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 as the training set.

###  D.4 Exact numerical results of our experiments

|  |  | Cross Entropy | Poly-tailed Loss
---|---|---|---|---
|  |  | mean | std. err. | mean | std. err. |  $p$-value
Dataset |  | Setting |  |  |  |  |
Subsampled CelebA | Early-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-ES | 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 CIFAR10 | Early-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-Exp-ES | 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 1: Numerical results corresponding to Figure 4 and 4. Here “Exp” corresponds to exponentiated weights. We use $3/2$ and $2$ as the exponents in Binary CIFAR10 and CelebA respectively. We use $\alpha=1$ for all of these experiments without tuning $\alpha$. Setting |  Summary of method |  Best settings |  Mean test acc |  Std err
---|---|---|---|---
Cross Entropy |  |  N/A |  60.5% |  0.8%
Cross Entropy + IW |  Classical importance weighting |  N/A |  57.8% |  0.4%
Cross Entropy + Class undersampling |  Balance the classes by throwing away majority data |  N/A |  58.5% |  1.4%
LDAM |  Add class dependent constants to logits |  largest margin=1.0 |  58.7% |  1.6%
CDT |  Multiply class dependent constants by logits |  $\gamma=0.5$ |  60.2% |  1.6%
LA Loss |  Add class dependent constants to logits |  $\tau=3$ |  66.9% |  2.1%
VS Loss (best setting around range suggested by paper) |  Multiply by and add class dependent constants to logits |  $\tau=1,\gamma=0.05$ |  58.6% |  1.4%
VS Loss (our own tuning) |  Multiply by and add class dependent constants to logits |  $\tau=3,\gamma=0.3$ |  69.3% |  0.9%
Poly-tailed Loss |  Change loss function and exponentiate importance weights |  $\alpha=2,\overline{w}^{3}$ |  67.3% |  0.8%
Table 2: Results on imbalanced binary CIFAR10, corresponding to Figure 5 (left). Setting |  Method summary |  Best settings |  Mean test acc |  Std err |  Worst group test acc |  Std err
---|---|---|---|---|---|---
Cross Entropy |  |  N/A |  79.6% |  1.2% |  43.1% |  2.9%
Cross Entropy + Group undersampling |  Balance the groups by throwing away overrepresented data |  N/A |  82.3% |  3.2% |  72.1% |  8.6%
Cross Entropy + IW |  Classical importance weighting |  N/A |  79.3% |  0.4% |  43.1% |  2.9%
VS Loss |  Multiply by and add class dependent constants to logits |  $\gamma=0.4$ |  82.6% |  0.7% |  51.3% |  1.5%
Poly-tailed Loss |  Change loss function and exponentiate importance weights |  $\alpha=2$, $\overline{w}^{2.5}$ |  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 |  $\gamma=0.4$ |  83.2% |  0.9% |  58.2% |  2.0%
Poly-tailed Loss + DRO |  Change loss function and use DRO |  $\alpha=2$ |  86.7% |  1.1% |  66.5% |  1.9%
Table 3: Results on subsampled CelebA, corresponding to Figure 5 (right)

## References

  * [BD90] Brian Beavis and Ian Dobbs  “Optimisation and stability theory for economic analysis”  Cambridge University Press, 1990
  * [BL19] Jonathon Byrd and Zachary Lipton  “What is the effect of importance weighting in deep learning?”  In _International Conference on Machine Learning_ , 2019, pp. 872–881
  * [Cao+19] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga and Tengyu Ma  “Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss”  In _Advances in Neural Information Processing Systems_ , 2019, pp. 1567–1578
  * [CGB21] Yuan Cao, Quanquan Gu and Mikhail Belkin  “Risk bounds for over-parameterized maximum margin classification on sub-Gaussian mixtures”  In _arXiv preprint arXiv:2104.13628_ , 2021
  * [CL21] Niladri S Chatterji and Philip M Long  “Finite-sample analysis of interpolating linear classifiers in the overparameterized regime”  In _Journal of Machine Learning Research_ 22.129, 2021, pp. 1–30
  * [Ji+20] Ziwei Ji, Miroslav Dudik, Robert E Schapire and Matus Telgarsky  “Gradient descent follows the regularization path for general losses”  In _Conference on Learning Theory_ , 2020, pp. 2109–2136
  * [JT19] Ziwei Ji and Matus Telgarsky  “The implicit bias of gradient descent on nonseparable data”  In _Conference on Learning Theory_ , 2019, pp. 1772–1798
  * [JT20] Ziwei Ji and Matus Telgarsky  “Directional convergence and alignment in deep learning”  In _Advances in Neural Information Processing Systems_ , 2020, pp. 17176–17186
  * [Jin09] Jiashun Jin  “Impossibility of successful classification when useful features are rare and weak”  In _Proceedings of the National Academy of Sciences_ 106.22, 2009, pp. 8859–8864
  * [Kin+21] Ganesh Ramachandra Kini, Orestis Paraskevas, Samet Oymak and Christos Thrampoulidis  “Label-Imbalanced and Group-Sensitive Classification under Overparameterization”  In _arXiv preprint arXiv:2103.01550_ , 2021
  * [LR21] Tengyuan Liang and Benjamin Recht  “Interpolating classifiers make few mistakes”  In _arXiv preprint arXiv:2101.11815_ , 2021
  * [LL19] Kaifeng Lyu and Jian Li  “Gradient descent maximizes the margin of homogeneous neural networks”  In _International Conference on Learning Representations_ , 2019
  * [Men+20] 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
  * [Mut+21] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu and Anant Sahai  “Classification vs regression in overparameterized regimes: Does the loss function matter?”  In _Journal of Machine Learning Research_ 22.222, 2021, pp. 1–69
  * [Nac+19] 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_ , 2019, pp. 3420–3428
  * [Sag+19] 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 generalization”  In _arXiv preprint arXiv:1911.08731_ , 2019
  * [Shi00] Hidetoshi Shimodaira  “Improving predictive inference under covariate shift by weighting the log-likelihood function”  In _Journal of Statistical Planning and Inference_ 90.2 Elsevier, 2000, pp. 227–244
  * [Sou+18] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar and Nathan Srebro  “The implicit bias of gradient descent on separable data”  In _Journal of Machine Learning Research_ 19.1, 2018, pp. 2822–2878
  * [Ver18] Roman Vershynin  “High-dimensional probability: An introduction with applications in data science”  Cambridge University Press, 2018
  * [WT21] Ke Wang and Christos Thrampoulidis  “Benign overfitting in binary classification of Gaussian mixtures”  In _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2021, pp. 4030–4034
  * [WYG14] Junfeng Wen, Chun-Nam Yu and Russell Greiner  “Robust learning under uncertain test distributions: Relating covariate shift to model misspecification”  In _International Conference on Machine Learning_ , 2014, pp. 631–639
  * [XYR20] Da Xu, Yuting Ye and Chuanwei Ruan  “Understanding the role of importance weighting for deep learning”  In _International Conference on Learning Representations_ , 2020
  * [Ye+20] Han-Jia Ye, Hong-You Chen, De-Chuan Zhan and Wei-Lun Chao  “Identifying and compensating for feature deviation in imbalanced deep learning”  In _arXiv preprint arXiv:2001.01385_ , 2020