Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks

Introduction

This paper focuses on an intriguing phenomena: overparameterized neural networks are surprisingly robust to label noise when first order methods with early stopping is used to train them. To observe this phenomena consider Figure 1 where we perform experiments on the MNIST data set. Here, we corrupt a fraction of the labels of the training data by assigning their label uniformly at random. We then fit a four layer model via stochastic gradient descent and plot various performance metrics in Figures 1(a) and 1(b). Figure 1(a) (blue curve) shows that indeed with a sufficiently large number of iterations the neural network does in fact perfectly fit the corrupted training data. However, Figure 1(a) also shows that such a model does not generalize to the test data (yellow curve) and the accuracy with respect to the ground truth labels degrades (orange curve). These plots clearly demonstrate that the model overfits with many iterations. In Figure 1(b) we repeat the same experiment but this time stop the updates after a few iterations (i.e. use early stopping). In this case the train accuracy degrades linearly (blue curve). However, perhaps unexpected, the test accuracy (yellow curve) remains high even with a significant amount of corruption. This suggests that with early stopping the model does not overfit and generalizes to new test data. Even more surprising, the train accuracy (orange curve) with respect to the ground truth labels continues to stay around $100\%$ even when $50\%$ of the labels are corrupted (see also and for related empirical experiments). That is, with early stopping overparameterized neural networks even correct the corrupted labels! These plots collectively demonstrate that overparameterized neural networks when combined with early stopping have unique generalization and robustness capabilities. As we detail further in Section 3 this phenomena holds (albeit less pronounced) for richer data models and architectures.

This paper aims to demystify the surprising robustness of overparameterized neural networks when early stopping is used. We show that gradient descent is indeed provably robust to noise/corruption on a constant fraction of the labels in such over-parameterized learning scenarios. In particular, under a fairly expressive dataset model and focusing on one-hidden layer networks, we show that after a few iterations (a.k.a. early stopping), gradient descent finds a model (i) that is within a small neighborhood of the point of initialization and (ii) only fits to the correct labels essentially ignoring the noisy labels. We complement these findings by proving that if the network is trained to overfit to the noisy labels, then the solution found by gradient descent must stray rather far from the initial model. Together, these results highlight the key features of a solution that generalizes well vs. a solution that fits well.

Our work is connected to recent advances on theory for deep learning as well as heuristics and theory surrounding outlier robust optimization.

Overparameterized neural networks: Intriguing properties and benefits of overparameterized neural networks has been the focus of a growing list of publications . A recent line of work shows that overparameterized neural networks can fit the data with random initialization if the number of hidden nodes are polynomially large in the size of the dataset. This line of work however is not informative about the robustness of the trained network against corrupted labels. Indeed, such theory predicts that (stochastic) gradient descent will eventually fit the corrupted labels. In contrast, our focus here is not in finding a global minima, rather a solution that is robust to label corruption. In particular, we show that with early stopping we fit to the correct labels without overfitting to the corrupted training data. Our result also differs from this line of research in another way. The key property utilized in this research area is that the Jacobian of the neural network is well-conditioned at a random initialization if the dataset is sufficiently diverse (e.g. if the points are well-separated). In contrast, in our model the Jacobian is approximately low-rank with the rank of the Jacobian corresponding to different clusters/classes within the dataset. We harness this low-rank nature to prove that gradient descent is robust to label corruptions. We further utilize this low-rank structure to explain why neural networks can work with much more modest amounts of overparameterization where the number of parameters grow with rank rather than the sample size. Furthermore, our numerical experiments verify that the Jacobian matrix of real datasets (such as CIFAR10) indeed exhibit low-rank structure. This is closely related to the observations on the Hessian of deep networks which is empirically observed to be low-rank . An equally important question for understanding the convergence behavior of optimization algorithms for overparameterized models is understanding their generalization capabilities. This is the subject of a few interesting recent papers . While in this paper we do not tackle generalization in the traditional sense, we do show that solutions found by gradient descent are robust to label noise/corruption which demonstrates their predictive capabilities and in turn suggests better generalization.

2 Models

We note that this definition allows for a fraction $\rho$ of corruptions in each cluster. Next we define the ground truth label function.

where the activation function $\phi$ applies entrywise. Given a dataset $\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}$, we shall train the network via minimizing the empirical risk over the training data via a quadratic loss

In particular, we will run gradient descent with a constant learning rate $\eta$, starting from a random initialization $\bm{W}_{0}$ via the following gradient descent updates

Main results

Let ${\bm{g}}\sim\mathcal{N}(0,{\bm{I}}_{d})$. Define the neural net covariance matrix ${\bm{{\Sigma}}}({\bm{C}})$ as

Here $\bigodot$ denotes the elementwise product. Also denote the minimum eigenvalue of ${\bm{{\Sigma}}}({\bm{C}})$ by $\lambda({\bm{C}})$.

One can view ${\bm{{\Sigma}}}({\bm{C}})$ as an empirical kernel matrix associated with the network where the kernel is given by $\mathcal{K}(\bm{c}_{i},\bm{c}_{j})={\bm{{\Sigma}}}_{ij}({\bm{C}})$. Note that ${\bm{{\Sigma}}}({\bm{C}})$ is trivially rank deficient if there are two cluster centers that are identical. In this sense, the minimum eigenvalue of ${\bm{{\Sigma}}}({\bm{C}})$ will quantify the ability of the neural network to distinguish between distinct cluster centers. The more distinct the cluster centers, the larger $\lambda(\bm{C})$ is. Throughout we shall assume that $\lambda({\bm{C}})$ is strictly positive. Related assumptions are empirically and theoretically studied in earlier works by . For instance, when the cluster centers are maximally diverse e.g. uniformly at random from the unit sphere $\lambda(\bm{C})$ scales like a constant (). Additionally, for ReLU activation, if the cluster centers are separated by a distance $\nu>0$, then $\lambda({\bm{C}})\geq\frac{\nu}{100K^{2}}$ ().

Now that we have a quantitative characterization of distinctiveness/diversity in place we are now ready to state our main result. Throughout we use $c_{\Gamma},C_{\Gamma}$, etc. to denote constants only depending on $\Gamma$. We note that this theorem is slightly simplified by ignoring logarithmic terms and precise dependencies on $\Gamma$. We refer the reader to Theorem 8.13 for the precise statement.

Eq. (2.1) applies to all training samples. Finally, for all $0\leq\tau\leq T$, the distance to initialization obeys

Theorem 2.2 shows that gradient descent with early stopping is robust and predicts correct labels despite constant corruption. $\varepsilon_{0}$ neighborhood of the cluster centers can be viewed as the test data since it corresponds to the support of the input distribution where data is sampled from. Further properties are discussed below.

This result is independent of number of clusters and only depends on number of classes. An interesting future direction is to improve this result to allow on the order of $n$ corrupted labels.

Early stopping time. We only need few iterations to find a good model: Using proposed step size, the iteration number is at most order $K$ and typically scales as $\max(1,K/d)$ up to condition numbers.

where $\bm{W}_{0}$ is the point of initialization for the gradient based algorithm that will be used to solve (2.2).

holds, we have $\left\|\bm{W}-\bm{W}_{0}\right\|\geq\frac{\delta}{C\Gamma\varepsilon_{0}}-\frac{t}{1000}$.

In words, this result shows that in order to fit to a dataset with a single corrupted label, a randomly initialized network has to traverse a distance of at least $\delta/\varepsilon_{0}$. Lemma 6.1 in the supplementary clarifies the role of the corruption amount $\rho$ and shows that more label corruption within a fixed class requires a model with a larger norm in order to fit the labels.

Can we really overfit to corruption? A natural question is whether early stopping is necessary i.e. can we perfectly interpolate to the corrupted dataset model of Definition 1.2. The recent works on neural net optimization answers this affirmatively. In particular, as long as no two input samples are not identical, sufficiently wide neural networks trained with gradient descent can provably and perfectly interpolate a corrupted dataset.

2 Key Technical Ideas

Our key proof idea is that semantically meaningful datasets (such as the clusterable dataset model) should have a low-dimensional representation. We use Jacobian mapping of the neural network to capture such structure in data. Specifically, we leverage the approximate low-rankness of the Jacobian matrix

We show that the optimization is implicitly decomposed into two stages which corresponds to the column subspaces induced by the large and small singular values of the Jacobian. First, denoting the overall network prediction by $f(\bm{W})=[f(\bm{W},\bm{x}_{1})~\dots~(\bm{W},\bm{x}_{n})]^{T}$, we represent the residual as

Under our dataset model, we prove that clean residual is aligned with the large singular subspace whereas label noise is aligned with the small subspace. As a result, gradient descent learns the useful information (clean residual) in few iterations whereas it takes much longer to overfit to noise justifying the use of early stopping.

Numerical experiments

We conduct several experiments to investigate the robustness capabilities of deep networks to label corruption. In our first set of experiments, we explore the relationship between loss, accuracy, and amount of label corruption on the MNIST dataset to corroborate our theory. Our next experiments study the distribution of the loss and the Jacobian on the CIFAR-10 dataset. Finally, we simulate our theoretical model by generating data according to the corrupted data model of Definition 1.2 and verify the robustness capability of gradient descent with early stopping in this model.

In Figure 3, we train the same model used in Figure 1 with $n=3,000$ MNIST samples for different amounts of corruption. Our theory predicts that more label corruption leads to a larger distance to initialization. To probe this hypothesis, Figure 3(a) and 3(b) visualizes training accuracy and training loss as a function of the distance from the initialization. These results demonstrate that the distance from initialization gracefully increase with more corruption.

Next, we study the distribution of the individual sample losses on the CIFAR-10 dataset. We conducted two experiments using Resnet-20 with cross entropy loss We used cross entropy as it is the standard classification loss however least-squares achieves similar accuracy.. In Figure 4(a) and 4(b) we assess the noise robustness of gradient descent where we used all 50,000 samples with either 30% random corruption or 50% random corruption. Theorem 5.1 predicts that when the corruption level is small, the loss distribution of corrupted vs. clean samples should be separable. Figure 4(a) shows that when 30% of the data is corrupted the distributions are approximately separable. When we increase the shuffling amount to 50% in Figure 4(b), the training loss on the clean data increases as predicted by our theory and the distributions start to gracefully overlap.

As we briefly discussed in Section 2.2 (see proofs in the supplementary for more extensive discussion), our technical framework utilizes a bimodal prior on the Jacobian matrix (7.2) of the model. We now further investigate this hypothesis. For a binary class task, size of the Jacobian matrix is sample size ($n$) $\times$ total number of parameters in the model ($p$). The neural network model we used for CIFAR 10 has around $p=270,000$ parameters in total. In Figure 4(c) we illustrate the singular value histogram of binary Jacobian model where the training classes are Airplane and Automobile. We trained the model with all samples and focus on the histogram of all training data ($n=10,000$) before and after the training. In particular, only 10 to 20 singular values are larger than $0.1\times$ the top one. This is consistent with earlier works that studied the Hessian spectrum. Another intriguing finding is that the distribution of before and after training are fairly close to each other highlighting that even at random initialization, the Jacobian spectrum exhibits bimodal structure.

Conclusions

In this paper, we studied the robustness of overparameterized neural networks to label corruption from a theoretical lens. We provided robustness guarantees for training networks with gradient descent when early stopping is used and complemented these guarantees with lower bounds. Our results point to the distance between final and initial network weights as a key feature to determine robustness vs. overfitting which is inline with weight decay and early stopping heuristics. We also carried out extensive numerical experiments to verify the theoretical predictions as well as technical assumptions. While our results shed light on the intriguing properties of overparameterized neural network optimization, it would be appealing (i) to extend our results to deeper network architecture, (ii) to more complex data models, and also (iii) to explore other heuristics that can further boost the robustness of gradient descent methods.

Acknowledgements

Authors would like to thank Yoav Freund for pointing out an issue with numerical experiments in the first draft of this manuscript. M. Soltanolkotabi is supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship in Mathematics, an NSF-CAREER under award #1846369, the Air Force Office of Scientific Research Young Investigator Program (AFOSR-YIP) under award #FA9550-18-1-0078, an NSF-CIF award #1813877, and a Google faculty research award.

References

Improvements for perfectly cluster-able data

We would like to note that in the limit of $\epsilon_{0}\rightarrow 0$ where the input data set is perfectly clustered one can improve the amount of overparamterization. Indeed, the result above is obtained via a perturbation argument from this more refined result stated below.

Consier the setting and assumptions of Theorem 5.1 with $\epsilon_{0}=0$. Starting from an initial weight matrix $\bm{W}_{0}$ selected at random with i.i.d. $\mathcal{N}(0,1)$ entries we run gradient descent updates of the form $\bm{W}_{\tau+1}=\bm{W}_{\tau}-\eta\nabla\mathcal{L}(\bm{W}_{\tau})$ on the least-squares loss (1.3) with step size $\eta\leq\frac{K}{2c_{up}n\Gamma^{2}\left\|{\bm{C}}\right\|^{2}}$. Furthermore, assume the number of hidden nodes obey

with $\lambda(\bm{C})$ is the minimum cluster per Definition 2.1. Then, with probability at least $1-2/K^{100}$ over randomly initialized $\bm{W}_{0}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,1)$, the iterates $\bm{W}_{\tau}$ obey the following properties.

The distance to initial point $\bm{W}_{0}$ is upper bounded by

After $\tau\geq\tau_{0}:=c{\frac{K}{\eta n\lambda({\bm{C}})}}\log\left(\frac{\Gamma\sqrt{n\log K}}{\rho}\right)$ iterations, the entrywise predictions of the learned network with respect to the ground truth labels $\{\widetilde{y}_{i}\}_{i=1}^{n}$ satisfy

for all $1\leq i\leq n$. Furthermore, if the noise level $\rho$ obeys $\rho\leq\delta/8$ the network predicts the correct label for all samples i.e.

To (over)fit to corrupted labels requires straying far from initialization

obeys $\|{\bm{W}}\|_{F}\geq\frac{\sqrt{s}\delta}{5\Gamma\varepsilon_{0}}$ with probability at least $1-e^{-d/2}$.

Unlike Theorem 2.3 this result lower bounds the network norm in lieu of the distance to the initialization $\bm{W}_{0}$. However, using the triangular inequality we can in turn get a guarantee on the distance from initialization $\bm{W}_{0}$ via triangle inequality as long as $\|{\bm{W}_{0}}\|_{F}\lesssim{\cal{O}}({\sqrt{s}\delta/\varepsilon_{0}})$ (e.g. by choosing a small $\varepsilon_{0}$).

The above Theorem implies that the model has to traverse a distance of at least

to perfectly fit corrupted labels. In contrast, we note that the conclusions of the upper bound in Theorem 2.2 show that to be able to fit to the uncorrupted true labels the distance to initialization grows at most by $\tau\varepsilon_{0}$ after $\tau$ iterates. This demonstrates that there is a gap in the required distance to initialization for fitting enough to generalize and overfitting. To sum up, our results highlight that, one can find a network with good generalization capabilities and robustness to label corruption within a small neighborhood of the initialization and that the size of this neighborhood is independent of the corruption. However, to fit to the corrupted labels, one has to travel much more, increasing the search space and likely decreasing generalization ability. Thus, early stopping can enable robustness without overfitting by restricting the distance to the initialization.

Technical Approach and General Theory

which can also be written in the more compact form

To solve this problem we run gradient descent iterations with a constant learning rate $\eta$ starting from an initial point $\bm{\theta}_{0}$. These iterations take the form

Here, $\mathcal{J}(\bm{\theta})$ is the $n\times p$ Jacobian matrix associated with the nonlinear mapping $f$ defined via

Our approach is based on the hypothesis that the nonlinear model has a Jacobian matrix with bimodal spectrum where few singular values are large and remaining singular values are small. This assumption is inspired by the fact that realistic datasets are clusterable in a proper, possibly nonlinear, representation space. Indeed, one may argue that one reason for using neural networks is to automate the learning of such a representation (essentially the input to the softmax layer). We formalize the notion of bimodal spectrum below.

Spectrum over $\mathcal{S}_{+}$: For all $\bm{v}\in\mathcal{S}_{+}$ with unit Euclidian norm we have

Spectrum over $\mathcal{S}_{-}$: For all $\bm{v}\in\mathcal{S}_{-}$ with unit Euclidian norm we have

We will refer to $\mathcal{S}_{+}$ as the signal subspace and $\mathcal{S}_{-}$ as the noise subspace.

When $\epsilon<<\alpha$ the Jacobian is approximately low-rank. An extreme special case of this assumption is where $\epsilon=0$ so that the Jacobian matrix is exactly low-rank. We formalize this assumption below for later reference.

When $\epsilon_{0}>0$ and the data points of each cluster are not the same as the cluster center we have the bimodal Jacobian structure of Assumption 1 where over $\mathcal{S}_{-}$ the spectral norm is small but nonzero.

In Section 3, we verify that the Jacobian matrix of real datasets indeed have a bimodal structure i.e. there are few large singular values and the remaining singular values are small which further motivate Assumption 2. This is inline with earlier papers which observed that Hessian matrices of deep networks have bimodal spectrum (approximately low-rank) and is related to various results demonstrating that there are flat directions in the loss landscape .

2 Meta result on learning with label corruption

Define the $n$-dimensional residual vector $\bm{r}$ where $\bm{r}(\bm{\theta})=\begin{bmatrix}f(\bm{x}_{1},\bm{\theta})-\bm{y}_{1}&\ldots&f(\bm{x}_{n},\bm{\theta})-\bm{y}_{n}\end{bmatrix}^{T}$. A key idea in our approach is that we argue that (1) in the absence of any corruption $\bm{r}(\bm{\theta})$ approximately lies on the subspace $\mathcal{S}_{+}$ and (2) if the labels are corrupted by a vector $\bm{e}$, then $\bm{e}$ approximately lies on the complement space. Before we state our general result we need to discuss another assumption and definition.

Additionally, to connect our results to the number of corrupted labels, we introduce the notion of subspace diffusedness defined below.

$\mathcal{S}_{+}$ is $\gamma$ diffused if for any vector $\bm{v}\in\mathcal{S}_{+}$

The following theorem is our meta result on the robustness of gradient descent to sparse corruptions on the labels when the Jacobian mapping is exactly low-rank. Theorem 5.1 for the perfectly clustered data ($\epsilon_{0}=0$) is obtained by combining this result with specific estimates developed for neural networks.

This result shows that when the Jacobian of the nonlinear mapping is low-rank, gradient descent enjoys two intriguing properties. First, gradient descent iterations remain rather close to the initial point. Second, the estimated labels of the algorithm enjoy sample-wise robustness guarantees in the sense that the noise in the estimated labels are gracefully distributed over the dataset and the effects on individual label estimates are negligible. This theorem is the key result that allows us to prove Theorem 5.1 when the data points are perfectly clustered ($\epsilon_{0}=0$). Furthermore, this theorem when combined with a perturbation analysis allows us to deal with data that is not perfectly clustered ($\epsilon_{0}>0$) and to conclude that with early stopping neural networks are rather robust to label corruption (Theorem 2.2).

Finally, we note that a few recent publication require the Jacobian to be well-conditioned to fit labels perfectly. In contrast, our low-rank model cannot perfectly fit the corrupted labels. Furthermore, when the Jacobian is bimodal (as seems to be the case for many practical data sets and neural network models) it would take a very long time to perfectly fit the labels and as demonstrated earlier such a model does not generalize and is not robust to corruptions. Instead we focus on proving robustness with early stopping.

3 To (over)fit to corrupted labels requires straying far from initialization

In this section we state a result that provides further justification as to why early stopping of gradient descent leads to more robust models without overfitting to corrupted labels. This is based on the observation that while finding an estimate that fits the uncorrupted labels one does not have to move far from the initial estimate in the presence of corruption one has to stray rather far from the initialization with the distance from initialization increasing further in the presence of more corruption. We make this observation rigorous below by showing that it is more difficult to fit to the portion of the residual that lies on the noise space compared to the portion on the signal space (assuming $\alpha\gg\epsilon$).

Denote the residual at initialization $\bm{\theta}_{0}$ by $\bm{r}_{0}=f(\bm{\theta}_{0})-\bm{y}$. Define the residual projection over the signal and noise space as

This theorem shows that the higher the corruption (and hence $E_{-}$) the further the iterates need to stray from the initial model to fit the corrupted data.

Proofs

We begin by defining the average Jacobian which will be used throughout our analysis.

Given gradient descent iterate $\hat{\bm{\theta}}=\bm{\theta}-\eta{\nabla{\cal{L}}(\bm{\theta})}$, define

The residuals $\hat{\bm{r}}=f(\hat{\bm{\theta}})-\bm{y}$, $\bm{r}=f(\bm{\theta})-\bm{y}$ obey the following equation

Proof Following Definition 8.1, denoting $f(\hat{\bm{\theta}})-\bm{y}=\hat{\bm{r}}$ and $f(\bm{\theta})-\bm{y}=\bm{r}$, we find that

Here (a) uses the fact that Jacobian is the derivative of $f$ and (b) uses the fact that ${\nabla{\cal{L}}(\bm{\theta})}={\cal{J}}(\bm{\theta})^{T}\bm{r}$.

Using Assumption 7.1, one can show that sparse vectors have small projection on $\mathcal{S}_{+}$.

Proof The proof will be done inductively over the properties of gradient descent iterates and is inspired from the recent work . In particular, requires a well-conditioned Jacobian to fit labels perfectly. In contrast, we have a low-rank Jacobian model which cannot fit the noisy labels (or it would have trouble fitting if the Jacobian was approximately low-rank). Despite this, we wish to prove that gradient descent satisfies desirable properties such as robustness and closeness to initialization. Let us introduce the notation related to the residual. Set $\bm{r}_{\tau}=f(\bm{\theta}_{\tau})-\bm{y}$ and let $\bm{r}_{0}=f(\bm{\theta}_{0})-\bm{y}$ be the initial residual. We keep track of the growth of the residual by partitioning the residual as $\bm{r}_{\tau}=\bm{\bar{r}}_{\tau}+\bar{\bm{e}}_{\tau}$ where

We claim that for all iterations $\tau\geq 0$, the following conditions hold.

Under the induction hypothesis (8.4), $\bm{\theta}_{\tau+1}\in{\cal{D}}$.

Proof Since range space of Jacobian is in $\mathcal{S}_{+}$ and $\eta\leq 1/\beta^{2}$, we begin by noting that

In the above, (a) follows from the fact that row range space of Jacobian is subset of $\mathcal{S}_{+}$ via Assumption 2. (b) follows from the definition of $\bm{\bar{r}}_{\tau}$. (c) follows from the upper bound on the spectral norm of the Jacobian over $\mathcal{D}$ per Assumption 2, (d) from the fact that $\eta\leq\frac{1}{\beta^{2}}$, (e) from $\alpha\leq\beta$. The latter combined with the triangular inequality and induction hypothesis (8.6) yields (after scaling (8.6) by $4/\alpha$)

concluding the proof of $\bm{\theta}_{\tau+1}\in\mathcal{D}$.

To proceed, we shall verify that (8.6) holds for $\tau+1$ as well. Note that, following Lemma 8.2, gradient descent iterate can be written as

Since both column and row space of ${\bm{C}}(\bm{\theta}_{\tau})$ is subset of $\mathcal{S}_{+}$, we have that

This shows the first statement of the induction. Next, over $\mathcal{S}_{+}$, we have

where the second line uses the fact that $\bar{\bm{e}}_{\tau}\in\mathcal{S}_{-}$ and last line uses the fact that $\bm{\bar{r}}_{\tau}\in\mathcal{S}_{+}$. To proceed, we need to prove that ${\bm{C}}(\bm{\theta}_{\tau})$ has desirable properties over $\mathcal{S}_{+}$, in particular, it contracts this space.

Proof The proof utilizes the upper bound on the learning rate. The argument is similar to the proof of Lemma 9.7 of . Suppose Assumption 3 holds. Then, for any $\bm{\theta}_{1},\bm{\theta}_{2}\in\mathcal{D}$ we have

where for (a) we utilized the induction hypothesis (8.6) and (b) follows from the upper bound on $\eta$. Now that (8.24) is established, using following lemma, we find

The $\beta^{2}$ upper bound directly follows from Assumption 2 by again noticing range space of Jacobian is subset of $\mathcal{S}_{+}$.

Proof For $\bm{r}\in\mathcal{S}_{+}$ with unit Euclidian norm, we have

Also, for any $\bm{r}$, by range space assumption $\bm{r}^{T}{\bm{A}}{\bm{C}}^{T}\bm{r}=\Pi_{\mathcal{S}_{+}}(\bm{r})^{T}{\bm{A}}{\bm{C}}^{T}\Pi_{\mathcal{S}_{+}}(\bm{r})$ (same for ${\bm{C}}{\bm{C}}^{T}$). Combined with above, this concludes the claim.

What remains is proving the final two statements of the induction (8.6). Note that, using the claim above and recalling (8.19) and using the fact that $\left\|{\cal{J}}(\bm{\theta}_{\tau+1},\bm{\theta}_{\tau})\right\|\leq\beta$, the residual satisfies

where we used the fact that $\eta\leq\frac{1}{2\beta^{2}}$. Now, using the fact that ${\cal{J}}(\bm{\theta}_{\tau}){\cal{J}}(\bm{\theta}_{\tau})^{T}\succeq\alpha^{2}{\bm{P}}_{\mathcal{S}_{+}}$, we have

which establishes the second statement of the induction (8.6). What remains is obtaining the last statement of (8.6). To address this, completing squares, observe that

On the other hand, the distance to initial point satisfies

Combining the last two lines (by scaling the second line by $\frac{1}{4}\alpha$) and using induction hypothesis (8.6), we find that

To conclude, note that since $\frac{\eta\alpha^{2}}{4}\leq 1/8$ (as $\eta\leq 1/2\beta^{2}$), we have

which is the advertised result. If $\bm{e}$ is $s$ sparse and $\mathcal{S}_{+}$ is diffused, applying Lemma 7.1 we have

1.2 Proof of Generic Lower Bound – Theorem 7.3

Proof Suppose $\bm{\theta}\in{\cal{D}}$ satisfies $\bm{y}=f(\bm{\theta})$. Define $\bm{J}_{\tau}={\cal{J}}((1-\tau)\bm{\theta}+\tau\bm{\theta}_{0})$ and $\bm{J}={\cal{J}}(\bm{\theta},\bm{\theta}_{0})=\int_{0}^{1}\bm{J}_{\tau}d\tau$. Since Jacobian is derivative of $f$, we have that

Now, define the matrices $\bm{J}_{+}=\Pi_{\mathcal{S}_{+}}(\bm{J})$ and $\bm{J}_{-}=\Pi_{\mathcal{S}_{-}}(\bm{J})$. Using Assumption 1, we bound the spectral norms via

To proceed, projecting the residual on $\mathcal{S}_{+}$, we find for any $\bm{\theta}$ with $f(\bm{\theta})=\bm{y}$

If we set $R=\frac{E_{+}}{\beta}$, we can hope that solution will learn only the signal and does not overfit to the noise. The next section builds on this intuition and formalizes our algorithmic guarantees.

2 Proofs for Neural Networks

Throughout, ${\sigma_{\min}(\cdot)}$ denotes the smallest singular value of a given matrix. We first introduce helpful definitions that will be used in our proofs.

The following theorem is borrowed from and characterizes three key properties of the neural network Jacobian. These are smoothness, spectral norm, and minimum singular value at initialization which correspond to Lemmas 6.6, 6.7, and 6.8 in that paper.

Let $C>0$ be an absolute constant. As long as

At random Gaussian initialization $\bm{W}_{0}\sim\mathcal{N}(0,1)^{k\times d}$, with probability at least $1-1/K^{100}$, we have

At random Gaussian initialization $\bm{W}_{0}\sim\mathcal{N}(0,1)^{k\times d}$, with probability at least $1-1/K^{100}$, we have

is obtained by duplicating the rows of $\left\|\mathcal{J}(\widetilde{\bm{W}},{\bm{C}})-\mathcal{J}(\bm{W},{\bm{C}})\right\|$ by at most $c_{up}n/K$ times. Hence the spectral norm is scaled by at most $\sqrt{c_{up}n/K}$.

holds with probability at least $1-K^{-100}$.

for some constant $c>0$, concluding the proof.

We first prove a lemma regarding the projection of label noise on the cluster induced subspace.

We shall also pick the minimum singular value over $\mathcal{S}_{+}$ to be

We wish to verify Assumption 2 over the radius of

neighborhood of $\bm{W}_{0}$. What remains is ensuring that Jacobian over $\mathcal{S}_{+}$ is lower bounded by $\alpha$. Our choice of $k$ guarantees that at the initialization, with probability $1-K^{-100}$, we have

Suppose $LR\leq\alpha=\alpha_{0}/2$. Using triangle inequality on Jacobian spectrum, for any $\bm{W}\in{\cal{D}}$, using $\|{\bm{W}-\bm{W}_{0}}\|_{F}\leq R$, we would have

Overall, the assumptions of Theorem 7.2 holds with stated $\alpha,\beta,L$ with probability $1-2K^{-100}$ (union bounding initial residual and minimum singular value events). This implies for all $\tau>0$ the distance of current iterate to initial obeys

The final step is the properties of the label corruption. Using Lemma 8.10, we find that

Substituting the values corresponding to $\alpha,\beta,L$ yields that, for all gradient iterations with

This implies that if $\rho\leq\delta/8$, the network will miss the correct label by at most $\delta/2$, hence all labels (including noisy ones) will be correctly classified.

2.2 Proof of Theorem 2.3

Thus, denoting vectorization of a matrix by $\text{vect}(\cdot)$

Thus by the general mean value theorem there exists a point $(\widetilde{\bm{W}},\widetilde{\bm{x}})$ in the square $(\bm{W}_{0},\bm{x}_{1}),(\bm{W}_{0},\bm{x}_{2}),(\bm{W},\bm{x}_{1})$ and $(\bm{W},\bm{x}_{2})$ such that

Next we note that for a Gaussian random vector $\bm{g}\sim\mathcal{N}(\bm{0},\bm{I}_{d})$ we have

with probability at least $1-e^{-\frac{t^{2}}{2}}$.

3 Perturbation analysis for perfectly clustered data (Proof of Theorem 2.2)

Denote average neural net Jacobian at data ${\bm{X}}$ via

where reusing Schur’s result and boundedness of $|\phi^{\prime}|\leq\Gamma$

where $C_{1}\geq 1$ is a constant of our choice. Suppose input noise level $\varepsilon_{0}$ and number of hidden nodes obey

Then, for all gradient descent iterations satisfying $\tau\leq\tau_{0}$, we have that

Here $\beta$ is the upper bound on the Jacobian spectrum and $L$ is the spectral norm Lipschitz constant as in Theorem 8.8. Applying Lemma 8.11, note that

(where we used $\eta\tau_{0}\beta^{2}\geq 1$), for all $t\leq\tau_{0}$, we have that

The proof is by induction. Suppose it holds until $t\leq\tau_{0}-1$. At $t+1$, via (8.58) we have that

Right hand side holds since $L\leq\frac{1}{2\eta\tau_{0}\Theta}$. This establishes the induction for $d_{t+1}$.

Next, we show the induction on $p_{t}$. Observe that $3d_{t}+d_{t+1}\leq 10\tau_{0}\eta\Gamma\sqrt{n}\varepsilon_{0}\Theta(1+8\eta\tau_{0}\beta^{2})$. Following (8.64) and using $p_{t}\leq\Theta$, we need

Concluding the induction since $L$ satisfies the final line. Consequently, for all $0\leq t\leq\tau_{0}$, we have that

Next, note that, condition on $L$ is implied by

which is implied by $k\geq{\cal{O}}(\Gamma^{10}{\frac{K^{2}\|{\bm{C}}\|^{4}}{\lambda({\bm{C}})^{4}}}\log(\frac{\Gamma\sqrt{n\log K}}{\rho})^{6})$.

Finally, following (8.66), distance satisfies

Theorem 2.2 is obtained by the theorem below when we ignore the log terms, and treating $\Gamma$, $\lambda({\bm{C}})$ as constants. We also plug in $\eta=\frac{K}{2c_{up}n\Gamma^{2}\left\|{\bm{C}}\right\|^{2}}$.

Suppose $\rho\leq\delta/8$. Denote the total number of prediction errors with respect to true labels (i.e. not satisfying (5.1)) by $\text{err}(\bm{W})$. With same probability, $\text{err}(\bm{W}_{\tau})$ obeys

Finally, for any iteration count $0\leq t\leq\tau$ the total distance to initialization is bounded as

Hence, the total number of errors is at most

and applying Theorem 10.1 (which is a variation of Theorem 2.3), with probability at $1-K\exp(-100d)$, for all inputs $\bm{x}$ lying $\varepsilon_{0}$ neighborhood of cluster centers, we find that

hence, $\bm{W}_{\tau}$ outputs the correct decision for all samples.

Fourth statement – Distance: This follows from the triangle inequality

We have that right hand side terms are at most ${\cal{O}}(\Gamma\sqrt{\frac{K\log K}{\lambda({\bm{C}})}})$ and ${\cal{O}}(t\eta\varepsilon_{0}\frac{\Gamma^{4}Kn}{\lambda({\bm{C}})}\log(\frac{\Gamma\sqrt{n\log K}}{\rho})^{2})$ from Theorems 8.12 and 5.1 respectively. This implies (8.75).

Proof of Lemma 6.1

This implies the desired lower bound on $\|{\bm{W}}\|_{F}$.

Uniform guarantee for minimum distance

Assume $\left|\phi^{\prime}\right|,\left|\phi^{\prime\prime}\right|\leq\Gamma$ and $k\gtrsim d$. Suppose $\bm{W}_{0}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,1)$. Let $\bm{c}_{1},\dots,\bm{c}_{K}$ be cluster centers. Then, with probability at least $1-2e^{-(k+d)}-Ke^{-100d}$ over $\bm{W}_{0}$, any matrix $\bm{W}$ satisfying $\left\|\bm{W}-\bm{W}_{0}\right\|_{F}\lesssim\sqrt{k}$ satisfies the following. For all $1\leq i\leq K$,

To continue note that by the general mean value theorem there exists a point $(\overline{\bm{W}},\overline{\bm{x}})$ in the square $(\bm{W}_{0},\bm{x}),(\bm{W}_{0},\widetilde{\bm{x}}),(\bm{W},\bm{x}),$ and $(\bm{W},\widetilde{\bm{x}})$ such that

Next we note that for a Gaussian random vector $\bm{g}\sim\mathcal{N}(\bm{0},\bm{I}_{d})$ we have

To proceed, since $X_{\bm{x}}=f(\bm{W}_{0},\bm{x})$ is a Gaussian process, applying standard chaining bounds , we find

Combining this with (10.2), we conclude with the advertised bound.