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

Introduction

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, among others].

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,

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] 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] (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.

There has also been quite a bit of work on the non-asymptotic analysis of interpolating estimators. [LR20] provided a finite-sample upper bound the expected squared error for kernel “ridgeless” regressor, which interpolates the training data. [KLS20] provided an analysis of linear regression that emphasized the role of irrelevant variables as providing placeholders for learning parameters that play the role of slack variables. [BHX20] provided a finite-sample analysis of interpolating least-norm regression with feature selection. They showed that, beyond the point where the number of features included in the model exceeds the number of training examples, the excess risk decreases with the number of included features. This analysis considered the case that the covariates have a standard normal distribution. They also obtained similar results for a “random features” model. [Bar+20] provided non-asymptotic upper and lower bounds on the squared error for the OLS estimator; their analysis emphasized the effect of the covariance structure of the independent variables on the success or failure of this estimator. This earlier work studied regression; here we consider classification. Study of regression is facilitated by the fact that the OLS parameter vector has a simple closed-form expression as a function of the training data. [BHM18] studied the generalization error for a simplicial interpolating nearest neighbor rule. [BRT19] provided bounds on the generalization error for the Nadaraya-Watson regression estimator applied to a singular kernel, a method that interpolates the training data. [LRZ20] provided upper bounds on the population risk for the least-norm interpolant applied to a class of kernels including the Neural Tangent Kernel.

In concurrent independent work, [Mut+20] studied the generalization properties of the maximum margin classifier in the case where the marginal distribution on the covariates is a single Gaussian, rather than a Gaussian per class. They showed that, in this setting, if there is enough overparameterization, every example is a support vector, so that the maximum margin algorithm outputs the same parameters as the OLS algorithm. They also showed that the accuracy of the model, measured using the 0-1 test loss, can be much better than its accuracy with respect to the quadratic loss.

Additional related work is described in Section 6.

Definitions, Notation and Assumptions

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.

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

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

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:

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

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

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

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.

[DJ08] studied this model in the noise-free case (i.e. where $\eta=0$).

Our assumptions are also satisfied Strictly speaking, $x$ needs to be scaled down to make the sub-Gaussian norm less than $1$ for this to be true, but this does not affect the accuracy of the maximum margin classifier. by the following setting with Boolean attributes.

The noiseless setting of this model was studied by [HL12].

Main Result and Its Consequences

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

For all $0<\kappa<1$, there is an absolute constant $c>0$ such that, under the assumptions of Section 2, for all large enough $C$, with probability $1-\delta$, training on ${\cal S}$ produces a maximum margin classifier $w$ satisfying

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)$. 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$.

There is an absolute constant $c>0$ such that, under the assumptions of Section 2, in the noisy rare-weak model, for any $\gamma\geq 0$ and all large enough $C$, with probability $1-\delta$, training on ${\cal S}$ produces a maximum margin classifier $w$ satisfying

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$.

There is an absolute constant $c>0$ such that, under the assumptions of Section 2, in the Boolean noisy rare-weak model for any $0<\gamma<1/2$ and all large enough $C$, with probability $1-\delta$, training on ${\cal S}$ produces a maximum margin classifier $w$ satisfying

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].

Proof of Theorem 4

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$.

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.

There is an absolute positive constant $c$ such that

An application of the general Hoeffding’s inequality (see Theorem 16) upper bounds this probability and completes the proof. ∎

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$.

For all $0<\kappa<1$, there is an absolute positive constant $c$ such that, for all large enough $C$, with probability $1-\delta$ over the random choice of ${\cal S}$, it is linearly separable, and the maximum margin weight vector $w$ satisfies,

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

(of Theorem 4): Combine the result of Lemma 9 with the lower bound on $(\mu\cdot w)$ established in Lemma 10. ∎

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 We 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^{(t+1)}:=v^{(t)}-\alpha\nabla R(v^{(t)})$,

For any linearly separable $\mathcal{S}$ and for all small enough step-sizes $\alpha$, we have

For each index $k$ of an example, let $z_{k}:=y_{k}x_{k}$.

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.)

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

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.

There is an absolute constant $c$ such that, for all large enough $C$, and all small enough step sizes $\alpha$, for all iterations $t\geq 0$,

$A_{t}^{\text{max}}$ is the maximum ratio between a pair of samples at iteration $t$. Let $c_{1}$ be the constant $c\geq 1$ from Lemma 13. We will prove that $A_{t}^{\text{max}}\leq 4c_{1}^{2}$ for all $t\geq 0$ by using an inductive argument over the iterations $t$.

Assume that the inductive hypothesis holds for some iteration $t$, we shall now prove that then it must also hold at iteration $t+1$.

To simplify notation we shall analyze the ratio between the losses on the first and the second sample but a similar analysis holds for any distinct pair. Let $G_{t}$ be the loss on sample $z_{1}$ and let $H_{t}$ be the loss on sample $z_{2}$ at the $t^{th}$ iteration. Define $A_{t}:=G_{t}/H_{t}$ to be the ratio of the losses at iteration $t$.

By the definition of $v^{(t+1)}$ as the gradient descent iterate

Recalling that $c_{1}$ is the constant $c$ from Lemma 13, by (2), we have

These, combined with the the expression for $A_{t+1}$ above, give

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

where $(i)$ follows since the sum of the losses on all samples is always smaller than the initial loss which is $n$ (see Lemma 25) and $H_{t}\leq n$, while, $(ii)$ follows as the step-size may be chosen to be at most $(8c_{1}(p+2(\lVert\mu\rVert^{2}+\sqrt{p\log(n/\delta)})\lVert\mu\rVert^{2})n)^{-1}$.

Case 2 ($A_{t}>2c_{1}^{2}$) : Reusing inequality (4),

Since $p>C\lVert\mu\rVert^{2}$ and $p>Cn^{2}\log(n/\delta)$, and noting that Lemma 13 is consistent with $C$ being arbitrarily large while $c_{1}$ remains fixed, we have that, in this case, $A_{t+1}\leq A_{t}$ (as the term in the exponent is non-positive). This completes the proof of the inductive step in this case, and therefore the entire proof.

Armed with Lemma 14, we now prove Lemma 10.

Let us proceed assuming that the event defined in Lemma 13 occurs, and, in this proof, let $c_{1}$ be the constant $c$ from that lemma. We know that this event occurs with probability at least $1-\delta$.

Dividing the sum into the clean and noisy examples, we have

Since $|\mathcal{N}|\leq(\eta+c^{\prime})n$, where $c^{\prime}$ is an arbitrarily small constant, if $c_{2}$ is the constant from Lemma 14, we have

since $\eta\leq 1/C$. Thus inequality (10) implies

Now let us multiply both sides by $\lVert w\rVert/\lVert v_{t+1}\rVert$

Next, let us take the large-$t$ limit. Applying Lemma 11 to the left hand side,

By definition of the gradient descent iterates

This together with inequality (11) yields

Simulations

In the first experiment in Figure 2 we hold $n$ and the number of relevant attributes $s$ constant and vary the dimension $p$ for different values of $\gamma$. We find that after an initial dip in the test error (for $\gamma=0.2,0.3$) the test error starts to rise slowly with $p$, as in our upper bounds.

Next, in Figure 3 we explore the scaling of the test error with the number of relevant attributes $s$ when $n$ and $p$ are held constant. As we would expect, the test error decreases as $s$ grows for all the different values of $\gamma$.

Finally, in Figure 4 we study how the test error changes when both $p$ and $s$ are increasing when $n$ and $\gamma$ are held constant. Our results (see Corollary 6) do not guarantee learning when $s=\Theta(\sqrt{p})$ (and [Jin09] proved that learning is impossible in a related setting, even in the absence of noise); we find that the test error remains constant in our experiment in this setting. In the cases when $s=p^{0.55}$ and when $s=p^{0.65}$, slightly beyond this threshold, the test error approaches the Bayes-optimal error as $p$ gets large in our experiment. This provides experimental evidence that the maximum margin algorithm, without explicit regularization or feature selection, even in the presence of noise, learns with using a number of relevant variables near the theoretical limit of what is possible for any algorithm. [HL12, the fraction of relevant variables is going to zero as $p$ increases in these experiments.]

Additional Related Work

[NJ02] compared the Naive Bayes algorithm, which builds a classifier from estimates of class-conditional distributions using conditional independence assumptions, with discriminative training of a logistic regressor. Their main point is that Naive Bayes converges faster. Our analysis provides a counterpoint to theirs, showing that, for a reasonable data distribution that includes label noise, in the overparameterized regime, unregularized discriminative training with a commonly used loss function learns a highly accurate classifier from a constant number of examples.

The framework studied here also includes as a special case the setting studied by [HL12], with Boolean attributes; again, a key modification is the addition of misclassification noise. Also, while the upper bounds of [HL12] are for algorithms that perform unweighted votes over selected attributes, here we consider the maximum margin algorithm. A more refined analysis of learning with conditionally independent Boolean attributes was carried out by [BK15]. [KA18] studied learning with conditionally independent Boolean attributes in the presence of noise—they analyzed tasks other than classification, including estimating the degree of association between the attributes (viewed in that work as experts) and the true class designations.

As mentioned above, we consider the case that the data is corrupted with label noise. We consider adversarial label noise [KSS94, Kal+08, KLS09, ABL17, Tal20]. In this model, an adversary is allowed to change the classifications of an arbitrary subset of the domain whose probability is $\eta$, while leaving the marginal distribution on the covariates unchanged. It includes as a special case the heavily studied situation in which classifications are randomly flipped with probability $\eta$ [AL88, Kea98, Ces+99, Ser99, KS05, LS10, VMW15] along with variants that allow limited dependence of the probability that a label is corrupted on the clean example [Lug92, Nat+13, SBH13, CFS20]. Adversarial label noise allows for the possibility that noise is concentrated in a part of the domain, where noisy examples have greater potential to coordinate their effects; it is a weaker assumption than even Massart noise [MN06, BBM08, Awa+15, DGT19], which requires a separate limit on the conditional probability of an incorrect label, given any clean example. We show that, with sufficient overparameterization, even in the absence of regularity in the noise, the algorithm that simply minimizes the standard softmax loss without any explicit regularization enjoys surprisingly strong noise tolerance.

After a preliminary version of this paper was posted on arXiv [CL20], some related work was published [WT20, HMX21, LR21].

Discussion

Even in the presence of misclassification noise, with sufficient overparameterization, unregularized minimization of the logistic loss produces accurate classifiers when the clean data has well-separated sub-Gaussian class-conditional distributions.

We have analyzed the case of a linear classifier without a bias term. In the setting studied here, the Bayes-optimal classifier has a bias term of zero, and adding analysis of a bias term in the maximum margin classifier would complicate the analysis without significantly changing the results.

In the noisy rare-weak model, when $p$ and $s$ scale favorably with $n$, and $\gamma$ is a constant, the excess risk of the maximum margin algorithm decreases very rapidly with $n$. One contributing cause is a “wisdom of the crowds” effect that is present when classifying with conditionally independent attributes: a classifier can be very accurate, even when the angle between its normal vector and the optimum is not very small. For example, if $100$ experts each predict a binary class, and they are correct independently with probability $3/4$, a vote over their predictions remains over 95% accurate even if we flip the votes of $25$ of them. (Note that, even in some cases where Lemma 10 implies accuracy very close to optimal, it may not imply that the cosine of the angle between $\mu$ and $w$ is anywhere near $1$.) On the other hand, the concentration required for successful generalization is robust to departures from the conditional independence assumption. Our assumptions already allow substantial class-conditional dependence among the attributes, but it may be interesting to explore even weaker assumptions.

Our bounds show that the maximum margin classifier approaches the Bayes risk as the parameters go to infinity in various ways. It would be interesting to characterize the conditions under which this happens. A related question is to prove lower bounds in terms of the parameters of the problem. Another is to prove bounds for finite $p$ and $n$ under weaker conditions.

We assume that the distributions of $x-\mu$ and $x-(-\mu)$ are the same. This is useful in particular for simplifying the analysis of dot products between examples of opposite classes. It should not be difficult to extend the analysis meaningfully to remove this assumption—we use this assumption in this paper to keep the analysis as simple and clean as possible.

The lower bounds on $p$ are needed for concentration, as described earlier. We suspect that the requirement that $p=\Omega(n^{2}\log(n/\delta))$ can be improved. The bottleneck is in the proof of Lemma 14. (As we mentioned earlier, a larger value of $p$ promotes the property that the loss on an example can be reduced by gradient descent without increasing the loss on other examples very much.)

The lower bound on $\lVert\mu\rVert^{2}$ allows us to focus on the case where most clean examples are classified correctly by a large margin, which is the case that we want to focus on. This could potentially be weakened or removed through a case analysis, exploiting the fact that a weaker bound is needed in the case that $\lVert\mu\rVert$ is small.

Using the generalized Hoeffding bound (Theorem 16) it is not hard to show [HL12, Theorem 1] that, in our setting, the Bayes optimal classifier has error at most $\eta+\exp(-c\lVert\mu\rVert^{2})$ for an absolute constant $c$, and Slud’s Lemma gives a similar lower bound [AB09] [HL12, inequality (8)]. Our upper bound of $\eta+\exp(-c^{\prime}\lVert\mu\rVert^{4}/p)$ for the maximum margin algorithm applied to finite training data is worse than this by a factor of $\lVert\mu\rVert^{2}/p$ in the exponent.

Implicit regularization lemmas like the one that was so helpful to us have been obtained for other problems [Gun+17, Gun+18a, Woo+20, Azu+21]. We hope that further advances in implicit regularization research could be combined with the techniques of this paper to prove generalization guarantees for interpolating classifiers using richer model classes, including neural networks.

We thank anonymous reviewers for their valuable comments and suggestions. NC gratefully acknowledges the support of the NSF through grants IIS-1619362 and IIS-1909365.

Appendix A Concentration Inequalities

In this section we begin by presenting a definition of sub-Gaussian and sub-exponential random variables in terms of Orlicz norms. Then we state a version of Hoeffding’s inequality and a version of Bernstein’s inequality. Finally, we prove Lemma 13 which implies that a good event which our proofs rely on holds with high probability.

For an excellent reference of sub-Gaussian and sub-exponential concentration inequalities we refer the reader to [Ver18, Chapter 2].

A random variable $\theta$ is sub-Gaussian if

is bounded. Further, $\lVert\theta\rVert_{\psi_{2}}$ is defined to be its sub-Gaussian norm.

We now state general Hoeffding’s inequality [Ver18, Theorem 2.6.3] a concentration inequality for a weighted sum of independent sub-Gaussian random variables.

where $K=\max_{i}\lVert\theta_{i}\rVert_{\psi_{2}}$ and $c_{2}$ is an absolute constant.

A one-sided version of this theorem (upper/lower deviation bound) holds without the factor of $2$ multiplying the exponent on the right hand side.

A random variable $\theta$ is said to be sub-exponential if

is bounded. Further, $\lVert\theta\rVert_{\psi_{1}}$ is defined to be its sub-exponential norm.

We shall also use Bernstein’s inequality [Ver18, Theorem 2.8.1] a concentration inequality for a sum of independent sub-exponential random variables.

For independent mean-zero sub-exponential random variables $\theta_{1},\ldots,\theta_{m}$, for every $t>0$, we have

Again note that a one-sided version of this inequality holds without the factor of $2$ multiplying the exponent on the right hand side.

We break the proof of Lemma 13 into different parts, which are proved in separate lemmas. Lemma 13 then follows by a union bound.

For all $\kappa>0$, there is a $c\geq 1$ such that, for all large enough $C$, with probability at least $1-\delta/6$, for all $k\in[n]$,

For any clean sample $z_{i}$, the random variables $(z_{ij}-\mu_{j})^{2}$ are sub-exponential with norm

with probability at least $1-\delta/(6n)$.

By Young’s inequality for products, $\lVert z_{i}-\mu\rVert^{2}\leq 2\lVert z_{i}\rVert^{2}+2\lVert\mu\rVert^{2}$. Also recall that by assumption $\lVert\mu\rVert^{2}<p/C$. Combining this with the left hand side in the display above, for large enough $C$, we have

Again by Young’s inequality $\lVert z_{i}\rVert^{2}=\lVert z_{i}-\mu+\mu\rVert^{2}\leq 2\lVert z_{i}-\mu\rVert^{2}+2\lVert\mu\rVert^{2}$. Therefore,

A similar argument also holds for all noisy samples by considering the random variables $(z_{k}-(-\mu))$. Hence, by taking a union bound over all samples completes the proof. ∎

There is a $c\geq 1$ such that, for all large enough $C$, with probability at least $1-\delta/6$, for all $i\neq j\in[n]$,

For any pair $i,j\in[n]$ of indices of examples, we have

If we regard $\xi_{j}$ as fixed, and only $\xi_{i}$ as random, Theorem 16 gives

for $c_{3}=c_{2}/4$. Substituting into inequality (14), we infer

Taking a union bound over all pairs for the first term, and all individuals for the second term, we get

Choosing $t=c\sqrt{p\log(n/\delta)}$ for a large enough value of $c$, we have

For any $i$, clean or noisy, Hoeffding’s inequality implies

Since $\lVert\mu\rVert^{2}\geq C\log(n/\delta)$, this implies

Therefore, by taking a union bound over all $i\in\{1,\ldots,n\}$

Both the events in (15) and (16) will simultaneously hold with probability at most $\delta/6$. Assume that the event complementary to this bad event occurs, then for any distinct pair $z_{i}$ and $z_{j}$

For all large enough $C$, with probability at least $1-\delta/6$,

since $\lVert\mu\rVert^{2}>C\log(n/\delta)$. Taking a union bound over all clean points establishes the claim. ∎

For all large enough $C$, with probability at least $1-\delta/6$,

For all $c^{\prime}>0$, for all large enough $C$, with probability $1-\delta/6$ the number of noisy samples satisfies $\lvert\mathcal{N}\rvert\leq(\eta+c^{\prime})n$.

Since $n\geq C\log(1/\delta)$, this follows from a Hoeffding bound. ∎

If (2) and (20) hold, then, if $C$ is large enough, $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ are linearly separable.

Let $v:=\sum_{k=1}^{n}z_{k}$. For each $k$ and any $\delta>0$,

for $p\geq C\max\{\lVert\mu\rVert^{2}n,n^{2}\log(n/\delta)\}$, completing the proof. ∎

Appendix B Decreasing Loss

For all small enough step sizes $\alpha$, for all iterations $t$, $R(v^{(t)})\leq n$.

Since $R(v^{(0)})=\sum_{j\in[n]}\exp\left(0\cdot z_{j}\right)=n$, it suffices to prove that, for all $t$, $R(v^{(t+1)})\leq R(v^{(t)})$. Toward showing this, note that, if $c_{1}$ is the constant $c$ from Lemma 13, the operator norm of the Hessian at any solution $v$ may be bound as follows:

This implies that $R$ is $c_{1}pn$-smooth over those $v$ such that $R(v)\leq n$. This implies that, for $\alpha\leq(c_{1}pn)^{-1}$, if $R(v^{(t)})\leq n$ then $R(v^{(t+1)})\leq R(v^{(t)})\leq n$ [JT19]. The lemma then follows using induction. ∎

References