The Implicit Bias of Benign Overfitting

Introduction

The ability of learning algorithms to succeed despite overfitting is a curious phenomenon in statistical learning, which has received much interest in the past few years. A particular version of it, commonly denoted as “benign overfitting” (Bartlett et al., 2020), refers to situations which combine the following: (1) The trained predictor interpolates the data, in the sense that it achieves perfect prediction accuracy on the training data; (2) No predictor in the relevant hypothesis class can achieve perfect accuracy w.r.t. the underlying data distribution; yet (3) The trained predictor has near-optimal accuracy w.r.t. the underlying data distribution. The combination of $(1)$ and $(2)$ implies that the predictor overfits (in the sense that the training error is significantly smaller than the test error), and $(3)$ implies that this overfitting is “benign” (in the simple sense that the predictor still performs well). This phenomenon is intriguing, because some version of it appears to occur frequently in large-scale learning problems, yet it cannot be easily explained using standard learning theoretic tools such as uniform convergence (which requires the performance on the training data and the underlying distribution to be similar). This has led to a flurry of papers in the past few years, attempting to understand why and when benign overfitting occurs, and whether uniform convergence can or cannot explain its occurence (see discussion of related work below).

Beginning with linear regression, we show that once the distribution is not well-specified, the minimum-norm interpolating predictor (a.k.a. min-norm predictor) returned by standard training methods will generally not be consistent, and hence benign overfitting will generally not occur. A bit more concretely, in our data model a consistent predictor $\hat{\mathbf{w}}$ should be such that asymptotically,

where $\mathbf{x}_{|d-k}$ are the last $d-k$ coordinates of $\mathbf{x}$. Clearly, the expressions in Eq. (1) and Eq. (2) are generally not the same, except in some special cases (an important one, as we shall see, being a well-specified setting). Thus, we argue that one should not expect benign overfitting to generally occur in linear regression with the square loss.

We show that benign overfitting will generally not occur in some natural extensions of linear regression with the square loss, even in a well-specified setting. These include (1) regression with generalized linear models (or equivalently, with a single neuron predictor); and (2) regression with losses other than the square loss. To do so, we present a new observation that may be of independent interest. Roughly speaking, we argue that any interpolating predictor can be seen as returning the optimum of the average loss, but simultaneously, it is also the optimum of many other types of average loss objectives, which reflect rather different learning problems with different optimal predictors. The trained predictor does not “know” which of these learning problems it is actually solving, so benign overfitting (with the trained predictor achieving low expected loss) can only occur in some of them. As a result, benign overfitting is implicitly “biased” towards certain learning problems, and its occurence in one problem precludes its occurence in another. We note that this is somewhat reminiscent of the paper Muthukumar et al. (2021), which pointed out that interpolating predictors can be insensitive to the type of loss function used for training, but we take this in a rather different direction.

Having discussed regression problems, we turn to binary classification problems (where our goal is to minimize misclassification error), and show that the situation there is rather different. Concretely, we consider linear predictors under the same data model as before, and the max-margin predictor $\hat{\mathbf{w}}$ (to which gradient-based methods are known to asymptotically converge in direction). Perhaps surprisingly, we prove that $\hat{\mathbf{w}}$ has a rather clean asymptotic characterization: Its first $k$ coordinates asymptotically minimize the expectation of a (weighted) squared hinge loss on those coordinates,

(where $[z]_{+}:=\max\{0,z\}$), and the last $d-k$ coordinates of $\hat{\mathbf{w}}$ are asymptotically immaterial. Thus, we get that the existence of benign overfitting in our model is reduced to a simpler question: Whether the data distribution is such that minimizing the expectation of this weighted squared hinge loss is a good surrogate for minimizing misclassification error. Although not true in the worst case, it is reasonable to assume that it will be true in many cases, because this loss still encourages the sign of $\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}_{k}$ to accord with the output $y$. This is in contrast to regression, in which our results suggest that benign overfitting is more brittle. Also, we note that unlike many previous works on benign overfitting in classification, our result does not require that the distribution is such that the min-norm and max-margin predictors coincide. Based on this result, we study more specifically the case of linearly separable distributions with label noise, and provide a few positive results: For example, for just about any choice of distribution on the first $k$ coordinates, we will have benign overfitting at least for some positive amount of label noise. Moreover, under some stronger assumptions on the input distribution (e.g., a mixture of symmetric distributions), we will have benign overfitting for any non-trivial level of label noise.

Overall, we hope that the results provided in this paper will allow us to understand the phenomenon of benign overfitting beyond the settings studied so far.

The paper is structured as follows: After discussing related work below, we study linear regression with the square loss in Sec. 3, and other regression settings in Sec. 4. We then turn to classification problems in Sec. 5, and conclude with a discussion in Sec. 6. The formal proofs of all our results appear in Appendix A.

Papers such as (Zhang et al., 2017) popularized the notion that modern learning systems (such as deep learning) tend to perfectly fit the training data, while still performing well on test data. The literature on the theory of this phenomenon is by now very large, and we will only discuss here the papers most relevant to our work (see for example Belkin (2021) for a more comprehensive survey).

A line of works (e.g., Belkin et al. (2018a, b, b, 2019b); Mei and Montanari (2019); Liang and Rakhlin (2020); Belkin et al. (2019a)) showed that this phenomenon is not reserved to deep learning, and occurs already in linear and kernel learning. More recently, papers such as Bartlett et al. (2020); Hastie et al. (2019); Belkin et al. (2020) studied conditions for benign overfitting in linear regression with the square loss in a well-specified setting. In particular, Bartlett et al. (2020) considered general distributions, and showed how the occurrence of benign overfitting can be characterized in terms of the eigenvalues of the input covariance matrix, and how having many low-variance directions is in some sense necessary for benign overfitting to occur. Koehler et al. (2021); Zhou et al. (2021) showed how these results can be recovered and extended from a uniform convergence perspective, again for well-specified linear regression. Other works which study benign overfitting and its relationship to classical learning theory include Nagarajan and Kolter (2019); Negrea et al. (2020); Yang et al. (2021); Bartlett and Long (2021); Bachmann et al. (2021); Koehler et al. (2021); Zhou et al. (2020); Muthukumar et al. (2021).

Understanding benign overfitting in classification problems has been more challenging, since the max-margin predictor to which gradient-based methods are known to converge to (in direction) does not have a closed-form solution. Many of the existing works focus on settings where the max-margin predictor and the (closed-form) least squares predictor coincide (as originally argued in Muthukumar et al. (2021)). Wang and Thrampoulidis (2021) and Cao et al. (2021) use this to study a setting where the two classes are a symmetric mixture of Gaussian (or subgaussian) distributions, without label noise. Chatterji and Long (2021) studies a setting where the two classes are a mixture of two product distributions, and with label noise, by studying the trajectory of gradient descent on the training data. Montanari et al. (2019) considers classification problem where the inputs are Gaussian, and the labels are generated according to a logistic link function, and derives a formula for the asymptotic prediction error of the max-margin classifier, in a setting where the ratio of the dimension and the sample size converges to some fixed positive limit. Recently, Frei et al. (2022) managed to prove the existence of benign overfitting in two-layer neural networks with smoothed leaky ReLU activations, assuming the data comes from a mixture of two well-separated distributions. Other works studying benign overfitting and classification include Liang and Recht (2021); McRae et al. (2021); Poggio and Liao (2019); Thrampoulidis (2020); Hu et al. (2021); Wang et al. (2021).

Preliminaries

Convergence in probability and the law of large numbers. For the asymptotic results in our paper, we will often consider a sequence of real-valued random variables $\{X_{d}\}$ indexed by $d$, and say that they converge in probability to some fixed number $a$ (or $X_{d}\stackrel{{\scriptstyle P}}{{\rightarrow}}a$) if $\Pr(|X_{d}-a|\geq\epsilon)\stackrel{{\scriptstyle d\rightarrow\infty}}{{\longrightarrow}}0$ for all $\epsilon\geq 0$. Note that this slightly extends the usual notion of convergence in probability, in that we do not require the random variables to share the same probability space. In addition, we will often utilize the following version of the (weak) law of large numbers for such sequences:

In other words, the min-norm predictor $\hat{\mathbf{w}}_{d}$ is asymptotically optimal, in the sense that its expected loss converges to the best possible expected loss among linear predictors, as the sample size and $d$ diverge to infinity at an appropriate rate. Moreover, this holds despite overfitting, in the sense that the training error (which is ) does not converge to the (strictly positive) expected loss.

The max-margin predictor, and benign overfitting for classification. In linear binary classification problems, we consider distributions where the examples $(\mathbf{x},y)$ are such that $y\in\{-1,+1\}$, and the predictor (specified by a vector $\mathbf{w}$) is $\mathbf{x}\mapsto\text{sign}(\mathbf{x}^{\top}\mathbf{w})$. In this case, we generally care only about the direction of the predictor $\mathbf{w}$, and its expected misclassification error, namely $\Pr_{(\mathbf{x},y)}(y\mathbf{x}^{\top}\mathbf{w}\leq 0)$. Whereas in regression, standard methods converge to the minimum-norm interpolating predictor, the characterization in classification is a bit different. Concretely, using standard convex classification losses with exponential tails (such as the logistic or cross-entropy loss), it is by now well-known that gradient-based methods ran on the average loss w.r.t. a given dataset $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{m}$ converge in direction to the max-margin predictor

Note that this definition is similar to the one we had for regression (Definition 1), except that $R_{d}(\cdot)$ is defined with respect to misclassification error, and $\hat{\mathbf{w}}_{d}$ is now defined as the max-margin predictor.

Linear Regression with the Square Loss

which goes to zero as $d\rightarrow\infty$ sufficiently faster than $m$. Moreover, assuming $\|\mathbf{z}\|$ does not fluctuate too wildly, the empirical quantity $m\cdot\left(\frac{\mathbf{z}^{\top}\mathbf{z}^{\prime}}{\|\mathbf{z}\|^{2}}\right)^{2}$ will strongly concentrate around as $d\rightarrow\infty$.

The key take-away from this theorem is as follows: Assuming various ratios and empirical moments of the dataset are bounded, then

where $E\rightarrow 0$ as the inner products between pairs of vectors in $\{\mathbf{x}_{i|d-k}\}_{i=1}^{m}$ go to zero. Assuming this convergence to zero is sufficiently fast compared to $m$, that $m\rightarrow\infty$, and that the law of large numbers hold, we get that

As to $\hat{\mathbf{w}}_{|d-k}$, we effectively bound its norm by $\mathcal{O}(m)$, which scales with $m$ but not with the dimension. If the input distribution on the last $d-k$ coordinates is sufficiently high-dimensional, this implies that given a new sample $\mathbf{x}$, the contribution of $\mathbf{x}_{|d-k}^{\top}\hat{\mathbf{w}}_{|d-k}$ to the predicted value (namely $\mathbf{x}^{\top}\hat{\mathbf{w}}=\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}_{|k}+\mathbf{x}_{|d-k}^{\top}\hat{\mathbf{w}}_{|d-k}$) is asymptotically negligible. Thus, the asymptotic expression of $\hat{\mathbf{w}}_{|k}$ eventually determines the behavior of the learned predictor.

Before continuing, let us provide an informal and partial proof sketch, explaining where the approximate expression for $\hat{\mathbf{w}}_{|k}$ in Thm. 1 comes from. To that end, let $X$ be a matrix whose $i$-th row is $\mathbf{x}_{i}$, and $\mathbf{y}=(y_{1},\ldots,y_{m})$. By standard results, $\hat{\mathbf{w}}=\arg\min_{\mathbf{w}}\|\mathbf{w}\|:X\mathbf{w}=\mathbf{y}$ has the closed-form expression $X^{\top}(XX^{\top})^{-1}\mathbf{y}$. Letting $X_{|k}$ be the first $k$ columns of $X$, it follows that $\hat{\mathbf{w}}_{|k}=X_{|k}^{\top}((XX^{\top})^{-1}\mathbf{y})=X_{|k}^{\top}(X_{|k}X_{|k}^{\top}+X_{|d-k}X_{|d-k}^{\top})\mathbf{y}$. Suppose for simplicity that $\{\mathbf{x}_{i|d-k}\}_{i=1}^{m}$ are precisely orthogonal (so that $E=0$ in the theorem above, and $X_{|d-k}X_{|d-k}^{\top}$ equals a diagonal matrix $D$). As a result, we get $\hat{\mathbf{w}}_{|k}=X_{|k}^{\top}\left(X_{|k}X_{|k}^{\top}+D\right)^{-1}\mathbf{y}$. By the Woodbury matrix identity and some algebraic manipulations, this equals $\left(I+X_{|k}^{\top}D^{-1}X_{|k}\right)^{-1}X_{|k}^{\top}D^{-1}\mathbf{y}$, or equivalently,

2 Asymptotic Characterization of the min-norm predictor

Let us now turn to show how Thm. 1 can lead to a formal asymptotic characterization of the min-norm predictor $\hat{\mathbf{w}}$, in a statistical setting where the training data is sampled from some underlying distribution. To do so, we will need to impose assumptions on the distribution, which ensure that the perturbation matrix $E$ from Thm. 1 indeed converges to , and that the various quantities in the bounds are well-behaved. One such set of sufficient conditions is the following:

If we sample $m_{d}$ i.i.d. samples $\{\mathbf{x}_{i},y_{i}\}_{i=1}^{m_{d}}$ from $\mathcal{D}_{d}$, then with probability approaching $1$, $\{\mathbf{x}_{i}\}_{i=1}^{m_{d}}$ are linearly independent, and $\min_{i\in[m_{d}]}\|\mathbf{x}_{i|d-k}\|$ is at least some $c>0$ independent of $d$.

$m_{d}\cdot\|E\|\stackrel{{\scriptstyle P}}{{\rightarrow}}0$, where $E$ is as defined in Eq. (4).

Since the assumptions are rather technical, let us provide one simple example to keep in mind, which satisfies the above:

We remark that in the example, we require $\lim_{d\rightarrow\infty}\frac{m_{d}^{3}\log(d)}{d}=0$, which is a stronger assumption on the scaling of $d$ vs. $m_{d}$ compared to previous work on linear regression (which usually consider $m_{d}/d\rightarrow 0$ under similar distributional assumptions). On the flip side, the proof technique allows us to analyze more general settings which go beyond well-specified linear regression.

In any case, we emphasize that Assumption 1 applies far more broadly than Example 1: For instance, it generally applies to any spherically-symmetric distribution of $\mathbf{x}_{|d-k}$ (possibly dependent on $\mathbf{x}_{|k},y$) so that $\|\mathbf{x}_{|d-k}\|$ is bounded (or at least concentrated) in some fixed interval bounded away from . Also, Assumption 1 itself is not the most general possible, in the sense that it focuses on situations where $\|\mathbf{x}\|,y$ and $\frac{1}{\|\mathbf{x}_{|d-k}\|}$ are scaled so that they are essentially bounded independent of $d$. Moreover, using Thm. 1 above one can analyze even more general situations: For example, that the data norm scales with $d$, while only bounding various ratios between relevant quantities.

Under Assumption 1, let us now proceed to formally state our asymptotic characterization of the min-norm predictor:

Suppose $\{\mathcal{D}_{d}\}_{d=k+1}^{\infty}$ and $\{m_{d}\}_{d=k+1}^{\infty}$ satisfy Assumption 1. For any $d$, let $\hat{\mathbf{w}}_{d}=\arg\min\|\mathbf{w}\|:\forall i\in[m_{d}],~{}\mathbf{x}_{i}^{\top}\mathbf{w}=y_{i}$ be the min-norm predictor w.r.t. a training set of size $m_{d}$ sampled i.i.d. from $\mathcal{D}_{d}$. Then as $d\rightarrow\infty$, $\hat{\mathbf{w}}_{d}$ exists with probability approaching $1$, and satisfies

3 Implications for benign overfitting in regression

Having established this asymptotic characterization of $\hat{\mathbf{w}}$, we now turn to discuss its implications to benign overfitting in linear regression. Our bottom-line message is that in general, $\hat{\mathbf{w}}_{d}$ is asymptotically not an optimal predictor, and hence benign overfitting will not occur.

To see this, consider any sequence of distributions $\{\mathcal{D}_{d}\}$ as in Thm. 2. For any $\mathcal{D}_{d}$, the expected loss has the form

which now coincides with the optimal solution on the first $k$ coordinates. However, a well-specified distribution is the exception rather than the rule in practice.

Linear Regression Beyond the Square Loss

In the previous section, we studied linear regression with the square loss, with our main conclusion being that benign overfitting should not be expected in general, beyond well-specified distributions. In this section, we study what happens if we do focus on well-specified distributions, but consider more general regression problems (beyond linear regression with the square loss). We will see that here again, benign overfitting can generally fail to hold.

The corollary follows immediately from the observation that since $\sigma$ is invertible, $\hat{\mathbf{w}}_{d}$ is also the minimum-norm minimizer of $\frac{1}{m_{d}}\sum_{i=1}^{m_{d}}(\mathbf{x}_{i}^{\top}\mathbf{w}-\sigma^{-1}(y_{i}))^{2}=0$, and that the moment conditions in Assumption 1 are still satisfied if we replace $y$ by $\sigma^{-1}(y)$ (since $|\sigma^{-1}(y)|\leq c_{\sigma}(1+|y|)$ for some $c_{\sigma}>0$ dependent only on $\sigma$). Applying Thm. 2 on $\hat{\mathbf{w}}_{d}$ with $y$ replaced by $\sigma^{-1}(y)$, we get that

and plugging in $y=\sigma(\mathbf{x}_{|k}^{\top})+\xi$ results in the theorem.

Next, we go back to linear regression, but now assume that we use some convex loss which is not necessarily the square loss (say, the absolute loss). Here again, standard gradient methods trained on the average loss will generally converge to a min-norm interpolating predictor (thanks to convexity and Proposition 1). However, we cannot expect benign overfitting to occur in general for this predictor:

In Thm. 2, for linear regression with the square loss, we saw that $\hat{\mathbf{w}}_{d|k}$ asymptotically equals

This can be equivalently seen as the minimum-norm optimum of the objective function

and in terms of asymptotic behavior, it turns out that $\hat{\mathbf{w}}$ is actually “consistent” with respect to the statistical problem associated with the latter, weighted loss function, and not the former unweighted one.

Linear Binary Classification

The results in the previous section suggest that many natural extensions of well-specified linear regression with the square loss will generally not satisfy benign overfitting. These were all regression problems, where to get low loss the prediction value must be close to some optimal value.

In this section, we turn to consider binary linear classification setups, where we only care about the sign of $\mathbf{x}^{\top}\mathbf{w}$ rather than its exact value, and see that the situation there is much more favorable. As in the case of regression, we will focus on input distributions which can be decomposed to some arbitrary distribution on the first $k$ coordinates, and a high-dimensional distribution on the last $d-k$ coordinates (for example, a spherically symmetric distribution).

Thus, we see that $\hat{\mathbf{w}}_{|k}$ is essentially the minimizer of the empirical average of the (weighted) squared hinge loss discussed earlier, plus a certain regularization term which decays with the data size $m$. This is modified by a $(1+\epsilon_{\mathbf{v}})$ multiplicative parameter, where $|\epsilon_{\mathbf{v}}|\leq\epsilon_{0}$ converges uniformly to as $\|E\|\rightarrow 0$. As to $\hat{\mathbf{w}}_{|d-k}$, as in the case of regression, we bound its norm by an expression generally scaling with $m$ but not with $d$, which implies that its contribution to the prediction (assuming a high-dimensional distribution on these coordinates) is negligible as $d\rightarrow\infty$.

Before continuing, let us informally explain how this squared hinge loss arises in our analysis (with the formal proof deferred as usual to the appendix). To simplify matters, let us suppose that $\{\mathbf{x}_{i|d-k}\}_{i=1}^{m}$ are precisely orthogonal (so that $E=0$ in the theorem above). In that case, the max-margin predictor $\hat{\mathbf{w}}$ can be equivalently written as

For any fixed $\mathbf{w}_{|k}$, we therefore wish to make $\|\mathbf{w}_{|d-k}\|^{2}$ as small as possible, while satisfying the constraints, which can also be written as $\forall i\in[m],~{}y_{i}\mathbf{x}_{i|d-k}^{\top}\mathbf{w}_{|d-k}\geq 1-y_{i}\mathbf{x}_{i|k}^{\top}\mathbf{w}_{|k}$. Since $\{y_{i}\mathbf{x}_{i|d-k}\}_{i=1}^{m}$ are orthogonal, it is easy to see that we should pick $\hat{\mathbf{w}}_{|d-k}$ as follows: If $1-y_{i}\mathbf{x}_{i|k}^{\top}\mathbf{w}_{|k}\leq 0$, we should make $y_{i}\mathbf{x}_{i|d-k}^{\top}\mathbf{w}_{|d-k}=0$, and if $1-y_{i}\mathbf{x}_{i|k}^{\top}\mathbf{w}_{|k}>0$, we should make $y_{i}\mathbf{x}_{i|d-k}^{\top}\mathbf{w}_{|d-k}=1-y_{i}\mathbf{x}_{i|k}^{\top}\mathbf{w}_{|k}$. By orthogonality of the $\{\mathbf{x}_{i|d-k}\}_{i=1}^{m}$ vectors, it follows that the optimal $\hat{\mathbf{w}}_{|d-k}$ equals

Again by orthogonality, it follows that $\|\mathbf{w}_{|d-k}\|^{2}=\sum_{i}\frac{[1-y_{i}\mathbf{x}_{i|k}^{\top}\mathbf{w}_{|k}]_{+}^{2}}{\|\mathbf{x}_{i|d-k}\|^{2}}$. Plugging this into Eq. (6), we get that $\hat{\mathbf{w}}_{|k}$ equals

Substituting $\mathbf{v}$ instead of $\mathbf{w}_{|k}$ results in the expression for $\hat{\mathbf{w}}_{|k}$ appearing in the theorem (with $\epsilon_{\mathbf{v}}=0$). The proof of Thm. 3 essentially generalizes this argument to the case where $\{\mathbf{x}_{i|d-k}\}_{i=1}^{m}$ are only approximately orthogonal, and also provides a bound for $\|\hat{\mathbf{w}}_{|d-k}\|$.

2 Asymptotic Characterization of the Max-margin Predictor

Having established the perturbation bound in the previous section, let us now show how this can lead to an asymptotic characterization of the max-margin predictor, under suitable distributional assumptions. As in the case of regression, we present a set of sufficient conditions (which are not the most general possible):

With probability approaching $1$ over sampling $m_{d}$ samples from $\mathcal{D}_{d}$, the max-margin predictor $\hat{\mathbf{w}}_{d}$ exists, and $\max_{i\in[m_{d}]}\max\left\{\frac{1}{\|\mathbf{x}_{i|d-k}\|},\|\mathbf{x}_{i|d-k}\|\right\}~{}\leq~{}c$ for some constant $c>0$ independent of $d$.

$m_{d}\cdot\|E\|\stackrel{{\scriptstyle P}}{{\rightarrow}}0$, where $E$ is as defined in Eq. (5) w.r.t. an i.i.d. sample of size $m_{d}$ from $\mathcal{D}_{d}$.

it holds that $\inf_{\mathbf{v}}\limsup_{d}\left(g_{d}(\mathbf{v})-\inf_{\mathbf{u}}g_{d}(\mathbf{u})\right)=0$.

With these conditions at hand, we can now state our asymptotic characterization of the max-margin predictor, in terms of the expected (weighted) squared hinge loss function $g_{d}(\cdot)$ defined above:

Suppose $\{\mathcal{D}_{d}\}_{d=k+1}^{\infty}$ and $\{m_{d}\}_{d=k+1}^{\infty}$ satisfy Assumption 2. Then the max-margin predictor $\hat{\mathbf{w}}_{d}=\arg\min\|\mathbf{w}\|:\forall i\in[m_{d}],~{}y_{i}\mathbf{x}_{i}^{\top}\mathbf{w}\geq 1$ satisfies

It is interesting to note that the max-margin predictor is asymptotically characterized in terms of a squared hinge loss, even though this loss does not appear explicitly in its definition (and moreover, the max-margin predictor itself arises from training gradient-based methods on losses which are definitely not the squared hinge loss). Instead, the loss naturally arises from our analysis. We note that this loss achieves the same value as the square loss for examples $(\mathbf{x},y)$ where $\mathbf{x}^{\top}\hat{\mathbf{w}}_{d}=y$, but is otherwise distinct. Thus, there is no contradiction with previous results on benign overfitting in classification that focused on situations where the max-margin and min-norm predictors coincide.

3 Implications for Benign Overfitting in Classification

Our results imply that asymptotically, the max-margin predictor depends only on the joint distribution of $\mathbf{x}_{|k},\|\mathbf{x}_{|d-k}\|,y$. Thus, to simplify the discussion in the remainder of this section, we will assume this distribution is fixed for all $d$, and satisfies some mild conditions:

To give a simple example, consider the case where $\mathcal{D}_{d}$ is defined as some fixed distribution over $(\mathbf{x}_{|k},y)$, and the marginal distribution of $\mathbf{x}_{|d-k}$ is uniform over some origin-centered sphereOne can also consider the case of $\mathbf{x}_{|d-k}$ being a zero-mean Gaussian with covariance matrix $\frac{\sigma^{2}}{d-k}I$ for some $\sigma^{2}>0$, in which case $\|\mathbf{x}_{|d-k}\|$ will concentrate around $\sigma$. In the assumption, we slightly simplify this by assuming $\|\mathbf{x}_{|d-k}\|$ already has such a limit distribution.. Under this assumption, the function $g_{d}$ can be rewritten as

Our goal now will be to illustrate how our characterization allows us to prove that benign overfitting does occur in some classification setups, which to the best of our knowledge have not been explicitly studied before.

Under the conditions of Thm. 4 and Assumption 3, define $R_{d}(\mathbf{w})$ to equal $\Pr_{(\mathbf{x},y)\sim\mathcal{D}_{d}}(y\mathbf{x}^{\top}\mathbf{w}\leq 0)$. Also, suppose that the distribution of $(\mathbf{x}_{|k},y)$ corresponds to some linearly separable distribution $\mathcal{D}_{\text{clean}}$ with labels flipped with some probability $p\in(0,\frac{1}{2})$.

Then benign overfitting (as defined in Eq. (3)) holds under the following condition: The (unique) minimizer $\mathbf{w}_{p}^{*}$ of $L_{p}(\mathbf{w})$ satisfies $\Pr_{(\mathbf{x}_{|k},y)\sim\mathcal{D}_{\text{clean}}}(y\mathbf{x}_{|k}^{\top}\mathbf{w}_{p}^{*}\leq 0)=0$.

Focusing on such linearly-separable-with-label-noise distributions, we now turn to study some cases where the condition on $\mathbf{w}_{p}^{*}$ in Thm. 5 indeed holds. For example, the following theorem implies that under mild assumptions, just about any choice of distribution $\mathcal{D}_{\text{clean}}$ satisfies benign overfitting, for some non-trivial (distribution-dependent) regime of label noise. As far as we can surmise, this is not at all obvious from the original characterization of the max-margin predictor, where the data points appear as constraints and where introducing label noise changes these constraints in possibly complicated ways. However, using our characterization and properties of the squared hinge loss, the result follows from a rather straightforward continuity argument.

Fix any distribution $\mathcal{D}_{\text{clean}}$ over $(\mathbf{x}_{|k},z,y)$ satisfying Assumption 3, which is linearly separable w.r.t. $(\mathbf{x}_{|k},y)$, and where $\mathbf{x}_{|k}$ has bounded support. Then there exists some $a\in(0,\frac{1}{2})$ (dependent on $\mathcal{D}_{\text{clean}}$), such that for all $p\in(0,a)$, the minimizer $\mathbf{w}^{*}_{p}$ of $L_{p}(\cdot)$ satisfies $\Pr_{(\mathbf{x}_{|k},y)\sim\mathcal{D}_{\text{clean}}}(y\mathbf{x}_{|k}^{\top}\mathbf{w}^{*}_{p}\leq 0)=0$.

Intuitively, the proof proceeds by arguing that $\mathbf{w}^{*}_{p}$ is continuous in $p\in(0,\frac{1}{2})$, and as $p\rightarrow 0$, necessarily converges to some predictor which separates the data with positive margin. Hence, small perturbations of the predictor will maintain linear separability, and therefore $\mathbf{w}^{*}_{p}$ will remain a linear separator for small positive values of $p$.

This result holds for generic linearly separable distributions, but does not specify the amount of label noise under which benign overfitting occurs. In the following theorem, we identify one simple class of distributions where benign overfitting occurs with any amount of label noise up to $\frac{1}{2}$:

Fix any distribution $\mathcal{D}_{\text{clean}}$ on $(\mathbf{x}_{|k},z,y)$ satisfying Assumption 3, such that the distribution of $(\mathbf{x}_{|k},y)$ is linearly separable. Moreover, suppose that for some unit vector $\mathbf{u}$, and conditioned on any value of $y$, $\mathbf{u}^{\top}\mathbf{x}$ and $(I-\mathbf{u}\mathbf{u}^{\top})\mathbf{x}$ are mutually independent, and the distributions of $(I-\mathbf{u}\mathbf{u}^{\top})\mathbf{x}$ and $-(I-\mathbf{u}\mathbf{u}^{\top})\mathbf{x}$ are identical. Then for all $p\in(0,\frac{1}{2})$, the minimizer $\mathbf{w}^{*}_{p}$ of $L_{p}(\cdot)$ satisfies $\Pr_{\mathcal{D}_{\text{clean}}}(y\mathbf{x}_{|k}^{\top}\mathbf{w}^{*}_{p}\leq 0)=0$.

The conditions in the theorem refer to a situation where there is some distinguished direction $\mathbf{u}$, such that conditioned on $y$, $\mathbf{x}_{|k}=\beta\mathbf{u}+\mathbf{s}$ for some mutually independent random variables $\beta,\mathbf{s}$ where $\mathbf{s}$ is orthogonal to $\mathbf{u}$ and has a symmetric distribution. Examples where this occurs include any one-dimensional distribution, and a mixture of any two symmetric distributions with means in $\text{span}(\mathbf{u})$ (one for $y=1$ and one for $y=-1$, and assuming linear separability). Note that unlike most previous results on benign overfitting in classification, the distributions do not need to be identical nor satisfy any additional structural properties.

Discussion

In this paper, we presented several new results on benign overfitting, for both regression and classification. For linear regression with the square loss, we argued that benign overfitting should not be expected to hold in general, once we go beyond well-specified distributions. Moreover, we showed how this can be extended beyond linear regression with the square loss, by an argument proving how the existence of benign overfitting on some regression problems precludes its existence on other regression problems. On the more positive side, for classification problems, we showed that the max-margin is implicitly biased towards minimizing a weighted squared hinge loss w.r.t. the underlying distribution (at least in a model where an arbitrary $k$-dimensional distribution is concatenated with a high-dimensional distribution). We use it to show benign overfitting in various settings, by considering cases where this squared hinge loss is a good surrogate for the misclassification error.

Overall, we hope that our observations here will allow us to understand benign overfitting beyond the settings studied so far in the literature. For example, it would be interesting to identify other settings where the structure of the squared hinge loss means that the max-margin predictor will have benign overfitting properties. Moreover, our results focused on input distributions with a clean separation between a few “important” coordinates, and a high dimensional distribution on the other coordinates. Although this is a prototypical setting for benign overfitting, our insights can potentially be extended to other input distributions, and identifying them can be an interesting direction for future research.

This research is supported in part by European Research Council (ERC) grant 754705. We thank Gilad Yehudai and the anonymous JMLR reviewers for several very helpful comments and suggestions.

References

Appendix A Proofs

We will utilize the following matrix inverse perturbation result:

Let $A$ be some positive definite matrix with minimal eigenvalue $\lambda_{\min}(A)>0$. Then for any symmetric matrix $E$ of the same size such that $\|E\|\leq\frac{\lambda_{\min}(A)}{2}$, it holds that $A+E$ is invertible and

By Weyl’s inequality, $\lambda_{\min}(A+E)\geq\lambda_{\min}(A)-\|E\|\geq\frac{\lambda_{\min}(A)}{2}>0$, hence $A+E$ is invertible. Moreover, by the Woodbury matrix identity,

Noting that $\|A^{-1}\|=\frac{1}{\lambda_{\min}(A)}$ and $\|E\|\leq\frac{\lambda_{\min}(A)}{2}$, it follows that the above is at most $\frac{\frac{1}{\lambda_{\min}(A)^{2}}\|E\|}{1-\frac{1}{\lambda_{\min}(A)}\cdot\frac{\lambda_{\min}(A)}{2}}=\frac{2}{\lambda_{\min}(A)^{2}}\|E\|$. ∎

where $E$ is as defined in the theorem statement (namely, the off-diagonal entries of $X_{|d-k}X_{|d-k}^{\top}$), and

is a diagonal matrix. In what follows, it will be useful to note that $\lambda_{\min}(D)=\min_{i\in[m]}\|\mathbf{x}_{m|d-k}\|^{2}$.

Continuing, we have by the representation of $\hat{\mathbf{w}}$ above that

Considering the first $k$ and last $d-k$ coordinates separately, it follows that

where $E^{\prime}$ is as defined in Eq. (8).

Applying Lemma 5 with $A=D+X_{|k}X_{|k}^{\top}$ (noting that $\lambda_{\min}(D+X_{|k}X_{|k}^{\top})\geq\lambda_{\min}(D)=\min_{i\in[m]}\|\mathbf{x}_{i|d-k}\|^{2}>0$ and that we assume $\|E\|\leq\frac{\lambda_{\min}(D)}{2}$), it follows that $\|E^{\prime}\|\leq\frac{2}{\lambda_{\min}(D)^{2}}\|E\|$. As a result, and using the fact that the spectral norm is upper bounded by the Frobenius norm, we have

We now turn to analyze $X_{|k}^{\top}(D+X_{|k}X_{|k}^{\top})^{-1}\mathbf{y}$ and $X_{|d-k}^{\top}(D+X_{|k}X_{|k}^{\top})^{-1}\mathbf{y}$, starting with the first expression. Using the Woodbury matrix identity, we have

(note that $I+X_{|k}^{\top}D^{-1}X_{|k}$ is indeed invertible, since it is the sum of the identity matrix and a positive semidefinite matrix). This implies that

Combining this with Eq. (12) and the Cauchy-Schwarz inequality, it follows that

Combining the above with Eq. (10) using a triangle inequality, it follows that

Recalling that $\lambda_{\min}(D)=\min_{i\in[m]}\|\mathbf{x}_{i|d-k}\|^{2}$, the first bound in the theorem follows.

As to bound on $\|\mathbf{w}_{|d-k}\|$ in the theorem, recalling Eq. (11), we need to analyze the expression $X_{|d-k}^{\top}(D+X_{|k}X_{|k}^{\top})^{-1}\mathbf{y}$. By Cauchy-Schwarz, its norm is at most

Combining this with Eq. (11), it follows that

Recalling that $\lambda_{\min}(D)=\min_{i\in[m]}\|\mathbf{x}_{i|d-k}\|^{2}$, the second bound in the theorem follows.

A.2 Proof of Theorem 2

A.3 Proof of Lemma 4

A.4 Proof of Thm. 3

To continue, let us perform the variable change $\boldsymbol{\beta}=(D+E)\boldsymbol{\alpha}$ (which is valid since $D+E$ is invertible), so $\boldsymbol{\alpha}=(D+E)^{-1}\boldsymbol{\beta}$, and

By Lemma 5 and the assumption $\|E\|\leq\frac{\lambda_{\min}(D)}{2}$, it follows that

where $A\succeq B$ for symmetric matrices $A,B$ implies that $A-B$ is positive semidefinite. Plugging this back into Eq. (14), it follows that

Plugging this into the previous displayed equation, it follows that

Noting that $\sum_{i=1}^{m}\frac{[r_{i}]_{+}^{2}}{D_{i,i}}=\|[D^{-1/2}\mathbf{r}]_{+}\|^{2}$ and plugging in the displayed equation above, the bound in the lemma follows. ∎

With this lemma in hand, we can now turn to prove the theorem. $\hat{\mathbf{w}}$ can be equivalently written as

where $E$ is as defined in the theorem statement, and $D$ being a diagonal matrix consisting of the diagonal of $Z_{|d-k}Z_{|d-k}^{\top}$ (namely $(\|\mathbf{x}_{1|d-k}\|^{2},\ldots,\|\mathbf{x}_{m|d-k}\|^{2})$), we can write the above as

Applying Lemma 6 on the equation above (and noting that $\|E\|<\frac{\lambda_{\min}(D)}{2}$, which follows from the assumption $\frac{2\|E\|\cdot\|D\|}{\lambda_{\min}(D)^{2}}=\frac{2\|E\|\cdot\max_{i\in[m]}\|\mathbf{x}_{i|d-k}\|^{2}}{\min{i\in[m]}\|\mathbf{x}_{i|d-k}\|^{4}}\leq\frac{1}{2}<1$ and the fact that $1\leq\frac{\|D\|}{\lambda_{\min}(D)}$), we get that

Plugging this back into Eq. (16), and plugging in $\frac{1}{m}\|[D^{-1/2}(\mathbf{1}-Z_{|k}\mathbf{v})]_{+}\|^{2}=\frac{1}{m}\sum_{i=1}^{m}\frac{[1-y_{i}\mathbf{x}_{i|k}^{\top}\mathbf{v}]_{+}^{2}}{\|\mathbf{x}_{i|d-k}\|^{2}}$ (which holds by definition of $D,Z_{|k}$), we get that

To get the second bound, note that since $\hat{\mathbf{w}}_{|k}$ minimizes the expression in Eq. (18), which for $\mathbf{v}=0$ equals $\frac{1+\epsilon_{\mathbf{v}}}{m}\sum_{i=1}^{m}\frac{1}{\|\mathbf{x}_{i|d-k}\|^{2}}\leq\frac{1+\epsilon_{0}}{\min_{i}\|\mathbf{x}_{i|d-k}\|^{2}}=\frac{1+\epsilon_{0}}{\lambda_{\min}(D)}$, it must hold that

and since $1+\epsilon_{\hat{\mathbf{w}}_{|k}}\geq 1-\epsilon_{0}>0$, it follows that

Next, recall from Eq. (16) and the fact that $(\hat{\mathbf{w}}_{|k},\hat{\mathbf{w}}_{|d-k})$ jointly optimize Eq. (15) that

Combining with Eq. (17) (with $\mathbf{v}=\hat{\mathbf{w}}_{|k}$), it follows that

where we recall that $\epsilon_{0}=\frac{2\|E\|\cdot\|D\|}{\lambda_{\min}(D)^{2}}$. Combining this with Eq. (19), we get

which is less than $5/\lambda_{\min}(D)$ (since $\epsilon_{0}\in[0,\frac{1}{2}]$). Multiplying both sides by $m$, and plugging in $\lambda_{\min}(D)=\min_{i\in[m]}\|\mathbf{x}_{i|d-k}\|^{2}$, results in the second bound in the theorem.

A.5 Proof of Thm. 4

Assumptions 2 and 3 imply that with probability approaching $1$ as $d$ increases, $\hat{\mathbf{w}}_{d}$ exists and the parameter $\epsilon_{0}$ from Thm. 3 is arbitrarily small. Under that event, Thm. 3 applies, and $\|\hat{\mathbf{w}}_{d|d-k}\|^{2}\leq c_{0}\cdot m_{d}$ for some $c_{0}>0$ independent of $d$. Therefore, with probability approaching $1$,

We now turn to analyze $\hat{\mathbf{w}}_{d|k}$, which by Thm. 3 and assumptions 2,3 satisfies

To justify this, let us compare $\hat{\mathbf{w}}_{d|k}$ to $\hat{\mathbf{v}}_{d}$, which we define as the minimum-norm minimizer ofA minimizer of $\hat{g}_{d}(\cdot)$ always exists, since it is convex piecewise-quadratic with finitely many pieces. The minimum-norm minimizer is unique, since if there were two minimizers of equal minimal norm, their average would also be a minimizer by convexity of $\hat{g}_{d}(\cdot)$, and with a smaller norm which is a contradiction. $\hat{g}_{d}(\cdot)$. By Eq. (20), we have with probability approaching $1$ for any large enough $d$ that

Multiplying both sides by $m_{d}$ and switching sides, it follows that

We now argue that all the terms in the bound above converge (deterministically or in probability) to : As to the first term, we know that $\sup_{\mathbf{v}}|\epsilon_{d,\mathbf{v}}|\stackrel{{\scriptstyle P}}{{\rightarrow}}0$, and $\hat{g}_{d}(\mathbf{v}_{0})$ is at most some fixed value independent of $d$ with probability approaching $1$, by assumption 2 and definition of $\hat{g}_{d}(\cdot)$. As to the second term, it converges to since $m_{d}\rightarrow\infty$. The third term converges in probability to as discussed above. As to the last term, we know that $\sup_{\mathbf{v}}|\epsilon_{d,\mathbf{v}}|\stackrel{{\scriptstyle P}}{{\rightarrow}}0$, and $\hat{g}_{d}(\hat{\mathbf{w}}_{d|k})$ is bounded by some constant independent of $d$ with probability approaching $1$ (since $\hat{\mathbf{w}}_{d_{k}}$ lies in some fixed compact set with probability approaching $1$ as discussed earlier, and the values of $\hat{g}_{d}(\cdot)$ are bounded independent of $d$ on any fixed compact set with probability approaching $1$, by assumption 2).

The displayed equation above and the following discussion implies that for any $\beta>0$, $\Pr(g_{d}(\hat{\mathbf{w}}_{d|k})-g_{d}(\mathbf{v}_{0})\geq\beta)\rightarrow 0$. This holds for any fixed $\mathbf{v}_{0}$. Combined with the assumption $\inf_{\mathbf{v}}\limsup_{d}(g_{d}(\mathbf{v})-\inf_{\mathbf{u}}g_{d}(\mathbf{u}))\leq 0$ (which implies that $\limsup_{d}(g_{d}(\mathbf{v}_{0})-\inf_{\mathbf{v}}g_{d}(\mathbf{v}))$ can be made arbitrarily small by choosing $\mathbf{v}_{0}$ appropriately), it follows that $\Pr(g_{d}(\hat{\mathbf{w}}_{d|k})-\inf_{\mathbf{v}}g_{d}(\mathbf{v})\geq\beta)\rightarrow 0$ for all $\beta>0$. But since $g_{d}(\hat{\mathbf{w}}_{d|k})-\inf_{\mathbf{v}}g_{d}(\mathbf{v})$ is necessarily non-negative, we get that $g_{d}(\hat{\mathbf{w}}_{d|k})-\inf_{\mathbf{v}}g_{d}(\mathbf{v})\stackrel{{\scriptstyle P}}{{\rightarrow}}0$.

A.6 Proof of Thm. 5

As discussed before the theorem, $L_{p}(\cdot)$ has a unique minimizer $\mathbf{w}^{*}_{p}$. Therefore, by Thm. 4, $\hat{\mathbf{w}}_{d|k}\stackrel{{\scriptstyle P}}{{\rightarrow}}\mathbf{w}^{*}_{p}$. Since we assume $\Pr_{(\mathbf{x}_{|k},y)\sim\mathcal{D}_{\text{clean}}}(y\mathbf{x}_{|k}^{\top}\mathbf{w}_{p}^{*}\leq 0)=0$, we argue that

Moreover, since $\hat{\mathbf{w}}_{d|k}\stackrel{{\scriptstyle P}}{{\rightarrow}}\mathbf{w}^{*}_{p}$, it holds that $y\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}_{d|k}\stackrel{{\scriptstyle P}}{{\rightarrow}}y\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}^{*}_{p}$ simultaneously for all vectors $y\mathbf{x}_{|k}$ of some bounded norm. Therefore, for any fixed $\gamma$,

Recalling that for any two events $E,A$ over some probability space,

Combined with Eq. (23) and Eq. (24), it follows that by picking $\gamma$ sufficiently small, we can make $\Pr_{(\mathbf{x}_{|k},y)\sim\mathcal{D}_{\text{clean}}}\left(y\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}_{d|k}\leq 0\right)$ asymptotically smaller than any positive number with arbitrarily high probability, from which Eq. (22) follows.

From Eq. (22) and the definition of $\mathcal{D}_{\text{clean}}$, it follows that

Combining the last two observations, we can use similar arguments as above to prove that

By applying Markov’s inequality on Eq. (25), it follows that for any $\gamma>0$, the measure of points $y\mathbf{x}\in\mathcal{U}^{d}_{\gamma}$ such that $|y\mathbf{x}^{\top}\hat{\mathbf{w}}_{d}-y\mathbf{x}^{\top}_{|k}\hat{\mathbf{w}}_{d|k}|>\frac{\gamma}{2}$ goes to in probability. For all other points in $\mathcal{U}^{d}_{\gamma}$, we have $y\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}_{d|k}>\gamma~{}\Rightarrow~{}y\mathbf{x}^{\top}\hat{\mathbf{w}}_{d}>\frac{\gamma}{2}$. Recalling that $y\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}_{d|k}\stackrel{{\scriptstyle P}}{{\rightarrow}}y\mathbf{x}_{|k}^{\top}\mathbf{w}^{*}_{p}$ (which is $>\gamma$) uniformly for all $y\mathbf{x}\in\mathcal{U}^{d}_{\gamma}$, we get that

A.7 Proof of Thm. 6

Note that any $\lambda$-strongly convex function is also $\lambda^{\prime}$ strongly convex for any $\lambda^{\prime}\in[0,\lambda]$. Also, it is well-known that any convex function is -strongly convex, that if $f$ is $\lambda$-strongly convex, then $c\cdot f$ is $c\cdot\lambda$-strongly convex, and that a sum of a $\lambda$-strongly convex function and a $\lambda^{\prime}$-strongly convex function is $(\lambda+\lambda^{\prime})$-strongly convex. Moreover, if $f$ is $\lambda$-strongly convex, it always has a finite unique minimizer $\mathbf{w}^{*}$, and $f(\mathbf{w})-f(\mathbf{w}^{*})\geq\frac{\lambda}{2}\|\mathbf{w}-\mathbf{w}^{*}\|^{2}$ for any $\mathbf{w}$.

Continuing, note that by the theorem’s assumptions,

Which by Eq. (27), implies that $L_{p}$ is $2p\lambda_{\min}$-strongly convex. ∎

We now continue with the proof of the theorem. Recall that

Now, let $B$ be such that $\Pr(\|y\mathbf{x}_{|k}\|\leq B)=1$ (such a $B$ exists by assumption). Note that since $\mathbf{w}^{*}_{p}\stackrel{{\scriptstyle p\rightarrow 0}}{{\longrightarrow}}\hat{\mathbf{w}}$, then for any $p>0$ sufficiently small, we must have $\|\mathbf{w}^{*}_{p}-\hat{\mathbf{w}}\|\leq\frac{1}{4B}$. For any $y,\mathbf{x}_{|k}$ such that $\|y\mathbf{x}_{|k}\|\leq B$, the event $y\mathbf{x}_{|k}^{\top}\mathbf{w}^{*}_{p}<\frac{1}{4}$ implies

But since we showed that $y\mathbf{x}_{|k}^{\top}\hat{\mathbf{w}}<\frac{1}{2}$ occurs with probability , it follows that the event $y\mathbf{x}_{|k}^{\top}\mathbf{w}^{*}_{p}<\frac{1}{4}$ also occurs with probability , namely

In particular, we get that for all sufficiently small $p$, the misclassification error probability of $\mathbf{w}^{*}_{p}$ is .

A.8 Proof of Thm. 7

and the the value of $L_{p}(\cdot)$ conditioned on any $y,z$ depends just on these quantities. But since $L_{p}(\cdot)$ is strongly convex, its minimizer must be unique, which is a contradiction.

for any $p\in(0,\frac{1}{2})$, which by convexity of $\beta\mapsto L_{p}(\beta\mathbf{u})$ implies that the (unique) minimizer $\mathbf{w}^{*}_{p}=\alpha_{p}\mathbf{u}$ of $L_{p}(\cdot)$ must satisfy $\alpha_{p}>0$. Overall, we have

Appendix B Minimizers of the Squared Hinge Loss Can Lead to Large Misclassification Error

where the expectation is with respect to the “clean” labels. In this case, the minimizer of the above might have an expected misclassification error of $1/2$ (even if $p$ is arbitrarily small). To see this, it is enough to produce some finite linearly-separable dataset, such that $50\%$ of the points will be misclassified by the minimizer of $L_{p}(\cdot)$ (and then random label flipping will keep the error rate at $50\%$). The existence of such a dataset was essentially shown for a more general setting in Long and Servedio , and below we instantiate their analysis for our setting with more explicit guarantees:

There exists a unit vector $\mathbf{w}^{*}$ for which $\min_{i}y_{i}\mathbf{x}_{i}^{\top}\mathbf{w}^{*}\geq p$

If $\hat{\mathbf{w}}$ is a minimizer of $L_{p}(\mathbf{w})~{}=~{}\frac{1}{4}\sum_{i=1}^{4}\left((1-p)\cdot[1-y_{i}\mathbf{x}_{i}^{\top}\mathbf{w}]_{+}^{2}+p\cdot[1+y_{i}\mathbf{x}_{i}^{\top}\mathbf{w}]_{+}^{2}\right)$, then $\hat{\mathbf{w}}$ misclassifies two of the four points.

It is easily verified that $\mathbf{w}^{*}=(p,0)$ satisfies $\min_{i}y_{i}\mathbf{x}_{i}^{\top}\mathbf{w}^{*}\geq p$. Also, by Lemma 7, it is easily verified that $L_{p}(\cdot)$ is strongly convex. Therefore, the minimizer is unique, and we claim that for any small enough $p>0$, it equals

In that case, for the two points $\mathbf{x}_{1}=\mathbf{x}_{2}=(p,-p)$,