Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime

A surprising statistical phenomenon has emerged in modern machine learning: highly complex models can interpolate training data while still generalizing well to test data, even in the presence of label noise. This is rather striking as it the goes against the grain of the classical statistical wisdom which dictates that predictors that generalize well should trade off between the fit to the training data and the some measure of the complexity or smoothness of the predictor. Many estimators like neural networks, kernel estimators, nearest neighbour estimators, and even linear models have been shown to demonstrate this phenomenon [Zha+17, Bel+19, see,].

This phenomenon has recently inspired intense theoretical research. One line of work [Sou+18, JT19, Gun+17, NSS19, Gun+18a, Gun+18] formalized the argument [NTS14, Ney17] that, even when there is no explicit regularization that is used in training these rich models, there is nevertheless implicit regularization encoded in the choice of the optimization method used. For example, in the setting of linear classification, [Sou+18], [JT19] and [NSS19] show that learning a linear classifier using gradient descent on the unregularized logistic or exponential loss asymptotically leads the solution to converge to the maximum $\ell_{2}$-margin classifier. More concretely, given $n$ linearly separable samples $(x_{i},y_{i})_{j=1}^{n}$, where $x_{i}\in\mathbb{R}^{p}$ are the features and $y_{i}\in\{-1,1\}$, the iterates of gradient descent (initialized at the origin) are given by,

They show that in the large-$t$ limit the normalized predictor obtained by gradient descent $v^{(t)}/\lVert v^{(t)}\rVert$ converges to $w/\lVert w\rVert$ where,

That is, $w$ is the maximum $\ell_{2}$-margin classifier over the training data.

The question still remains, though, why do these maximum margin classifiers generalize well beyond the training set, despite the fact that they “fit the noise”? The fact that $p>n$ renders traditional distribution-free bounds [Cov65, Vap82] vacuous. Due to the presence of label noise, margin bounds [Vap95, Sha+98] are also not an obvious answer.

In this paper, we prove an upper bound on the misclassification test error for the maximum margin linear classifier, and therefore on the the limit of gradient descent on the training error without any complexity penalty. Our analysis holds under a natural and fairly general generative model for the data. One special case is where adversarial label noise [KSS94, Kal+08, KLS09, ABL17, Tal20, see] is added to data in which the positive examples are distributed as $\mathsf{N}(\mu,I)$ and the negative examples are distributed $\mathsf{N}(-\mu,I)$. If $\lVert\mu\rVert$ is not too small, the clean data will consist of overlapping but largely separate clouds of points. Our assumptions are weaker than this, however (see Section 2 for the details). They are satisfied by the case in which misclassification noise is added to the generative model underlying Fisher’s linear discriminant [DHS12, HTF09, see] (except that, to make the analysis cleaner, the distribution is shifted so that the origin is halfway between the class-conditional means). They also include as special cases the rare-weak model [DJ08, Jin09] and a Boolean variant [HL12]. We study the overparameterized regime, when the dimension $p$ is significantly greater than the number $n$ of samples. For a precise statement of our main result see Theorem 4. After its statement, we give examples of its consequences, including cases in which $s$ of the $p$ variables are relevant, but weakly associated with the class designations. In some cases where $s$, $p$ and $n$ are polynomially related, the risk of the maximum-margin algorithm approaches the Bayes-optimal risk as $e^{-n^{\tau}}$, for $\tau>0$.

Analysis of classification is hindered by the fact that, in contrast to regression, there is no known simple expression for the parameters as a function of the training data. Our analysis leverages recent results, mentioned above, that characterize the weight vector obtained by minimizing the logistic loss on training data [Sou+18, JT19, NSS19]. We use this result not only to motivate the analysis of the maximum margin algorithm, but also in our proofs, to get a handle on the relationship of this solution to the training data. When learning in the presence of label noise, algorithms that minimize a convex loss face the hazard that mislabeled examples can exert an outsized influence. However, we show that in the over-parameterized regime this effect is ameliorated. In particular, we show that the ratio between the (exponential) losses of any two examples is bounded above by an absolute constant. One special case of our upper bounds is where there are relatively few relevant variables, and many irrelevant variables. In this case, classification using only parameters that correctly classify the clean examples with a large margin leads to large loss on examples with noisy class labels. However, the training process can use the parameters on irrelevant variables to play a role akin to slack variables, allowing the algorithm to correctly classify incorrectly labeled training examples with limited harm on independent test data. On the other hand, if there are too many irrelevant variables, accurate classification is impossible [Jin09]. Our bounds reflect this reality—if the number of irrelevant variables increases while the number and quality of the relevant variables remains fixed, ultimately our bounds degrade.

In simulation experiments, we see a decrease in population risk with the increase of $p$ beyond $n$, as observed in previous double-descent papers, but this is followed by an increase. As mentioned above, [Jin09] showed that, under certain conditions, if the number $p$ of attributes and the number $s$ of relevant attributes satisfy $p\geq s^{2}$, then, in a sense, learning is impossible. Our experiments suggest that interpolation with logistic loss can succeed close to this boundary, despite the lack of explicit regularization or feature selection.

Throughout this section, $C>0$ and $0<\kappa<1$ denote absolute constants. We will show that any choice $C$ that is large enough relative to $1/\kappa$ will work.

We study learning from independent random examples $(x,y)\in\mathbb{R}^{p}\times\{-1,1\}$ sampled from a joint distribution $\mathsf{P}$. This distribution may be viewed as a noisy variant of another distribution $\tilde{\mathsf{P}}$ which we now describe. A sample from $\tilde{\mathsf{P}}$ may be generated by the following process.

1. 1.

   First, a clean label $\tilde{y}\in\{-1,1\}$ is generated by flipping a fair coin.

2. 2.

   Next, $q\in\mathbb{R}^{p}$ is sampled from $\mathsf{Q}:=\mathsf{Q}_{1}\times\cdots\times\mathsf{Q}_{p}$, which is an arbitrary product distribution over $\mathbb{R}^{p}$

   • •

     whose marginals are all zero-mean sub-Gaussians with sub-Gaussian norm at most $1$ (see Definition 15), and

   • •

     such that $\mathbb{E}_{q\sim\mathsf{Q}}[\lVert q\rVert^{2}]\geq\kappa p$.

3. 3.

   For an arbitrary unitary matrix $U$ and $\mu\in\mathbb{R}^{p}$, $x=Uq+\tilde{y}\mu$. This ensures that the mean of $x$ is $\mu$ when $\tilde{y}=1$ and is $-\mu$ when $\tilde{y}=-1$.

4. 4.

   Finally, noise is modeled as follows. For $0\leq\eta\leq 1/C$, $\mathsf{P}$ is an arbitrary distribution over $\mathbb{R}^{p}\times\{-1,1\}$

   • •

     whose marginal distribution on $\mathbb{R}^{p}$ is the same as $\tilde{\mathsf{P}}$, and

   • •

     such that $d_{TV}(\mathsf{P},\tilde{\mathsf{P}})\leq\eta$.

   Note that this definition includes the special case where $y$ is obtained from $\tilde{y}$ by flipping it with probability $\eta$.

Choosing a bound of $1$ on the sub-Gaussian norm of the components of $\mathsf{Q}$ fixes the scale of the data. This simplifies the proofs without materially affecting the analysis, since rescaling the data does not affect the accuracy of the maximum margin algorithm.

Let $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ be $n$ training examples drawn according to $\mathsf{P}$. Let

When $\mathcal{S}$ is linearly separable, let $w\in\mathbb{R}^{p}$ minimize $\lVert w\rVert$ subject to $y_{1}(w\cdot x_{1})\geq 1,\ldots,y_{n}(w\cdot x_{n})\geq 1$. (In the setting that we analyze, we will show that, with high probability, $\mathcal{S}$ is linearly separable. When it is not, $w$ may be chosen arbitrarily.)

We will provide bounds on the misclassification probability of the classifier parameterized by $w$ that can be achieved with probability $1-\delta$ over the draw of the samples.

We make the following assumptions on the parameters of the problem:

1. (A.1)

   the failure probability satisfies $0\leq\delta<1/C$,

2. (A.2)

   number of samples satisfies $n\geq C\log(1/\delta)$,

3. (A.3)

   the dimension satisfies $p\geq C\max\{\lVert\mu\rVert^{2}n,n^{2}\log(n/\delta)\}$,

4. (A.4)

   the norm of the mean satisfies $\lVert\mu\rVert^{2}\geq C\log(n/\delta)$.

Here are some examples of generative models that fall within our framework.

Our main result is a finite-sample bound on the misclassification error of the maximum margin classifier.

Consider the scenario where the number of samples $n$ is a constant, but where the number of dimensions $p$ and $\lVert\mu\rVert$ are growing. Then our assumptions require $\lVert\mu\rVert^{2}=O(p)$.²²2 The definitions of “big Oh notation”, i.e. $O(\cdot)$, $\omega(\cdot)$, $\Theta(\cdot),\Omega(\cdot)$, may be found in [Cor+09]. But, for the misclassification error to decrease we need $\lVert\mu\rVert^{4}=\omega(p)$. Thus if, $\lVert\mu\rVert=\Theta(p^{\beta})$ for any $\beta\in(1/4,1/2]$ then as $p\to\infty$, the misclassification error asymptotically will approach the noise level $\eta$.

Here are the implications of our results in the noisy rare-weak model. Recall that in this model $\mu$ is non-zero only on $s$ coordinates and the non-zero coordinates of $\mu$ are equal to some $\gamma$. Therefore, $\lVert\mu\rVert^{2}=\gamma^{2}s$.

Next, let us examine the implications of our results in the Boolean noisy rare-weak model. Here, $\lVert\mu\rVert^{2}=4\gamma^{2}s$.

To gain some intuition let us explore the scaling of the misclassification error in these problems in different scaling limits for the parameters in both these problems.

Consider a case where, $\delta$, $\gamma$ and $n$ are constants and $s$ and $p$ grow. Our assumptions hold if $\lVert\mu\rVert^{2}=\gamma^{2}s=O(p)$. But for the misclassification error to decrease we need $s^{2}=\omega(p)$. So if $s=\Theta(p^{\beta})$ where, $\beta\in(1/2,1]$ then the misclassification error scales as $\eta+\exp(-cp^{2\beta-1})$ and asymptotically approaches $\eta$.

[Jin09] showed that for the noiseless rare-weak model learning is impossible when $s=O(\sqrt{p})$ and $n$ is a constant. Our upper bounds show that, in a sense, the maximum margin classifier succeeds arbitrarily close to this threshold.

Another interesting scenario is when $\delta$ and $\gamma$ are constants while both $s$ and $p$ grow as a function of the number of samples $n$. Let $p=\Theta(n^{2+\rho})$ and $s=\Theta(n^{1+\lambda})$, for positive $\rho$ and $\lambda$. Our assumptions are satisfied if $\rho>\lambda$ for large enough $n$, while, for the misclassification error to reduce with $n$ we need $2\lambda>\rho$. As $n$ gets larger the bound on the misclassification error scales as $\eta+\exp(-cn^{2\lambda-\rho})$ and gets arbitrarily close to $\eta$ for large enough $n$. Informally, if the adversary fully expends its noise budget, the Bayes error rate will be at least $\eta$; this is true in particular in the case where labels are flipped with probability $\eta$. In such cases, even if one could prove that the training data likely to be separated by a large margin, the bound of Theorem 4 approaches the Bayes error rate faster than the standard margin bounds [Vap95, Sha+98].

First, we may assume without loss of generality that $U=I$. To see this, note that

• •

  if $w$ is the maximum margin classifier for $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ then $Uw$ is the maximum margin classifier for $(Ux_{1},y_{1}),\ldots,(Ux_{n},y_{n})$, and

• •

  the probability that $y(w\cdot x)<0$ is the same as the probability that $y(Uw\cdot Ux)<0$.

Let us assume from now on that $U=I$.

Our first lemma is an immediate consequence of the coupling lemma [Lin02, Das11] that allows us to handle the noise in the samples.

Note that Lemma 7 implies that $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ are $n$ i.i.d. draws from $\mathsf{P}$, as before.

The next lemma is bound on the misclassification error in terms of the expected value of the margin on clean points, $\mathbb{E}_{(x,\tilde{y})\sim\mathsf{P}}[\tilde{y}(w\cdot x)]=\mu\cdot w$, and the norm of the classifier $w$.

In light of the previous lemma, next we prove a high probability lower bound on the expected margin on a clean point, $\mu\cdot w$.

Given these two main lemmas above, the main theorem follows immediately.

It remains to prove Lemma 10, a lower bound on the expected margin on clean points $(\mu\cdot w)$. This crucial lemma is proved through a series of auxiliary lemmas, which use a characterization of the maximum margin classifier $w$ in terms of iterates $\{v^{(t)}\}_{t=1}^{\infty}$ of gradient descent on the exponential loss. Denote the risk associated with the exponential loss³³3We could also work with the logistic loss here, but the proofs are simpler if we work with the exponential loss without changing the conclusions. as

Then the iterates of gradient descent are defined as follows:

• •

  $v^{(0)}:=0$, and

• •

  $v^{(t+1)}:=v^{(t)}-\alpha\nabla R(v^{(t)})$,

where $\alpha$ is a constant step-size.

Most of the argument required to prove Lemma 9 is deterministic apart from some standard concentration arguments, which are gathered in the following lemma. (Recall that, since we are in the process of proving Theorem 4, the assumptions of Section 2 are in scope.)

The proof of this lemma is in Appendix A.

From here on, we will assume that ${\cal S}$ satisfies all the conditions shown to hold with high probability in Lemma 13.

A concern is that, late in training, noisy examples will have outsized effect on the classifier learned. Lemma 14 below limits the extent to which this can be true. It shows that throughout the training process the loss on any one example is at most a constant factor larger than the loss on any other example. This is sufficient since the gradient of the exponential loss

is the sum of the $-z_{k}$ values weighted by their losses. We also know that with high probability $p/c\leq\lVert z_{k}\rVert\leq cp$, therefore, showing that the loss on a sample is within a constant factor of the loss of any other sample controls the influence that any one point can have on the learning process. We formalize this intuition in the proof of Lemma 10 in the sequel.

As will be clear in the proof of Lemma 14, the high dimensionality of the classifier ($p$ being larger than $\lVert\mu\rVert^{2}n$ and $n^{2}\log(n/\delta)$) is crucial in showing that the ratio of the losses between any pair of points is bounded. Here is some rough intuition why this is the case.

For the sake of intuition consider the extreme scenario where all the vectors $z_{k}$ are mutually orthogonal and $\lVert z_{i}\rVert=p$, for all $i\in[n]$. Then in this case, the change in the loss of a sample $i\in[n]$ due to each gradient descent update will be independent of any other sample $j\neq i\in[n]$ and all the losses will decrease exactly at the same rate. Lemma 13 implies that, when $p$ is large enough relative to $\lVert\mu\rVert$, the $z_{k}$ vectors are nearly pairwise orthogonal. In this case, the losses remain within a constant factor of one another.

We experimentally study the behavior of the maximum margin classifier in the overparameterized regime on synthetic data generated according to the Boolean noisy rare-weak model. Recall that this is a model where the clean label $\tilde{y}\in\{-1,1\}$ is first generated by flipping a fair coin. Then the covariate $x$ is drawn from a distribution conditioned on $\tilde{y}$ such that $s$ of the coordinates of $x$ are equal to $\tilde{y}$ with probability $1/2+\gamma$ and the other $p-s$ coordinates are random and independent of the true label. The noisy label $y$ is obtained by flipping $\tilde{y}$ with probability $\eta$. In this section the flipping probability $\eta$ is always $0.1$. In all our experiments the number of samples $n$ is kept constant at $100$.