Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data

Introduction

Neural networks have achieved great success in many applications, but despite a recent increase of theoretical studies, much remains to be explained. For example, it is empirically observed that learning with stochastic gradient descent (SGD) in the overparameterized setting (i.e., learning a large network with number of parameters larger than the number of training data points) does not lead to overfitting . Some recent studies use the low complexity of the learned solution to explain the generalization, but usually do not explain how the SGD or its variants favors low complexity solutions (i.e., the inductive bias or implicit regularization) . It is also observed that overparameterization and proper random initialization can help the optimization , but it is also not well understood why a particular initialization can improve learning. Moreover, most of the existing works trying to explain these phenomenons in general rely on unrealistic assumptions about the data distribution, such as Gaussian-ness and/or linear separability .

This paper thus proposes to study the problem of learning a two-layer overparameterized neural network using SGD for classification, on data with a more realistic structure. In particular, the data in each class is a mixture of several components, and components from different classes are well separated in distance (but the components in each class can be close to each other). This is motivated by practical data. For example, on the dataset MNIST , each class corresponds to a digit and can have several components corresponding to different writing styles of the digit, and an image in it is a small perturbation of one of the components. On the other hand, images that belong to the same component are closer to each other than to an image of another digit. Analysis in this setting can then help understand how the structure of the practical data affects the optimization and generalization.

In this setting, we prove that when the network is sufficiently overparameterized, SGD provably learns a network close to the random initialization and with a small generalization error. This result shows that in the overparameterized setting and when the data is well structured, though in principle the network can overfit, SGD with random initialization introduces a strong inductive bias and leads to good generalization.

Our result also shows that the overparameterization requirement and the learning time depends on the parameters inherent to the structure of the data but not on the ambient dimension of the data. More importantly, the analysis to obtain the result also provides some interesting theoretical insights for various aspects of learning neural networks. It reveals that the success of learning crucially relies on overparameterization and random initialization. These two combined together lead to a tight coupling around the initialization between the SGD and another learning process that has a benign optimization landscape. This coupling, together with the structure of the data, allows SGD to find a solution that has a low generalization error, while still remains in the aforementioned neighborhood of the initialization. Our work makes a step towrads explaining how overparameterization and random initialization help optimization, and how the inductive bias and good generalization arise from the SGD dynamics on structured data. Some other more technical implications of our analysis will be discussed in later sections, such as the existence of a good solution close to the initialization, and the low-rankness of the weights learned. Complementary empirical studies on synthetic data and on the benchmark dataset MNIST provide positive support for the analysis and insights.

Related Work

Generalization of neural networks. Empirical studies show interesting phenomena about the generalization of neural networks: practical neural networks have the capacity to fit random labels of the training data, yet they still have good generalization when trained on practical data . These networks are overparameterized in that they have more parameters than statistically necessary, and their good generalization cannot be explained by naïvely applying traditional theory. Several lines of work have proposed certain low complexity measures of the learned network and derived generalization bounds to better explain the phenomena. proved spectrally-normalized margin-based generalization bounds, derived bounds from a PAC-Bayes approach, and derived bounds from the compression point of view. They, in general, do not address why the low complexity arises. This paper takes a step towards this direction, though on two-layer networks and a simplified model of the data.

Overparameterization and implicit regularization. The training objectives of overparameterized networks in principle have many (approximate) global optima and some generalize better than the others , while empirical observations imply that the optimization process in practice prefers those with better generalization. It is then an interesting question how this implicit regularization or inductive bias arises from the optimization and the structure of the data. Recent studies are on SGD for different tasks, such as logistic regression and matrix factorization . More related to our work is , which studies the problem of learning a two-layer overparameterized network on linearly separable data and shows that SGD converges to a global optimum with good generalization. Our work studies the problem on data with a well clustered (and potentially not linearly separable) structure that we believe is closer to practical scenarios and thus can advance this line of research.

Theoretical analysis of learning neural networks. There also exists a large body of work that analyzes the optimization landscape of learning neural networks . They in general need to assume unrealistic assumptions about the data such as Gaussian-ness, and/or have strong assumptions about the network such as using only linear activation. They also do not study the implicit regularization by the optimization algorithms.

Problem Setup

In this work, a two-layer neural network with ReLU activation for $k$-classes classification is given by $f=(f_{1},f_{2},\cdots,f_{k})$ such that for each $i\in[k]$:

Let us define the support of a distribution $\mathcal{D}$ with density $p$ over $\mathcal{R}^{d}$ as $\text{supp}(\mathcal{D})=\{x:p(x)>0\},$ the distance between two sets $\mathcal{S}_{1},\mathcal{S}_{2}\subseteq\mathcal{R}^{d}$ as $\text{dist}(\mathcal{S}_{1},\mathcal{S}_{2})=\min_{x\in\mathcal{S}_{1},y\in\mathcal{S}_{2}}\{\|x-y\|_{2}\},$ and the diameter of a set $\mathcal{S}_{1}\subseteq\mathcal{R}^{d}$ as $\text{diam}(\mathcal{S}_{1})=\max_{x,y\in\mathcal{S}_{1}}\{\|x-y\|_{2}\}.$ Then we are ready to make the assumptions about the data.

(Separability) There exists $\delta>0$ such that for every $i_{1}\not=i_{2}\in[k]$ and every $j_{1},j_{2}\in[l]$, $\text{dist}\left(\text{supp}(\mathcal{D}_{i_{1},j_{1}}),\text{supp}(\mathcal{D}_{i_{2},j_{2}})\right)\geq\delta.$Moreover, for every $i\in[k],j\in[l]$,The assumption $1/(8l)$ can be made to $1/[(1+\alpha)l]$ for any $\alpha>0$ by paying a large polynomial in $1/\alpha$ in the sample complexity. We will not prove it in this paper because we would like to highlight the key factors. $\text{diam}(\text{supp}(\mathcal{D}_{i,j}))\leq\lambda\delta,~{}\text{for}~{}\lambda\leq 1/(8l).$

(Normalization) Any $x$ from the distribution has $\|x\|_{2}=1$.

A few remarks are worthy. Instead of having one distribution for one class, we allow an arbitrary $l\geq 1$ distributions in each class, which we believe is a better fit to the real data. For example, in MNIST, a class can be the number 1, and $l$ can be the different styles of writing $1$ ($1$ or $|$ or $/$).

Assumption (A2) is for simplicity, while (A1) is our key assumption. With $l\geq 1$ distributions inside each class, our assumption allows data that is not linearly separable, e.g., XOR type data in $\mathcal{R}^{2}$ where there are two classes, one consisting of two balls of diameter $1/10$ with centers $(0,0)$ and $(2,2)$ and the other consisting of two of the same diameter with centers $(0,2)$ and $(2,0)$. See Figure 3 in Appendix C for an illustration. Moreover, essentially the only assumption we have here is $\lambda=O(1/l)$. When $l=1$, $\lambda=O(1)$, which is the minimal requirement on the order of $\lambda$ for the distribution to be efficiently learnable. Our work allows larger $l$, so that the data can be more complicated inside each class. In this case, we require the separation to also be higher. When we increase $l$ to refine the distributions inside each class, we should expect the diameters of each distribution become smaller as well. As long as the rate of diameter decreasing in each distribution is greater than the total number of distributions, then our assumption will hold.

Assumptions about the learning process. We will only learn the weight $w_{r}$ to simplify the analysis. Since the ReLU activation is positive homogeneous, the effect of overparameterization can still be studied, and a similar approach has been adopted in previous work . So the network is also written as $y=f(x,w)=(f_{1}(x,w),\cdots,f_{k}(x,w))$ for $w=(w_{1},\cdots,w_{r})$.

We assume the learning is from a random initialization:

The learning process minimizes the cross entropy loss over the softmax, defined as:

Let $L(w,x_{s},y_{s})=-\log o_{y_{s}}(x_{s},w)$ denote the cross entropy loss for a particular point $(x_{s},y_{s})$.

We consider a minibatch SGD of batch size $B$, number of iterations $T=N/B$ and learning rate $\eta$ as the following process: Randomly divide the total training examples into $T$ batches, each of size $B$. Let the indices of the examples in the $t$-th batch be $\mathcal{B}_{t}$. At each iteration, the update isStrictly speaking, $L(w,x_{s},y_{s})$ does not have gradient everywhere due to the non-smoothness of ReLU. One can view $\frac{\partial L(w,x_{s},y_{s})}{\partial w_{r}}$ as a convenient notation for the right hand side of (1).

Main Result

Suppose the assumptions (A1)(A2)(A3) are satisfied. Then for every $\varepsilon>0$, there is $M=\text{poly}(k,l,1/\delta,1/\varepsilon)$ such that for every $m\geq M$, after doing a minibatch SGD with batch size $B=\text{poly}(k,l,1/\delta,1/\varepsilon,\log m)$ and learning rate $\eta=\frac{1}{m\cdot\text{poly}(k,l,1/\delta,1/\varepsilon,\log m)}$ for $T=\text{poly}(k,l,1/\delta,1/\varepsilon,\log m)$ iterations, with high probability:

Our theorem implies if the data satisfies our assumptions, and we parametrize the network properly, then we only need polynomial in $k,l,1/\delta$ many samples to achieve a good prediction error. This error is measured directly on the true distribution $\mathcal{D}$, not merely on the input data used to train this network. Our result is also dimension free: There is no dependency on the underlying dimension $d$ of the data, the complexity is fully captured by $k,l,1/\delta$. Moreover, no matter how much the network is overparameterized, it will only increase the total iterations by factors of $\log m$. So we can overparameterize by an sub-exponential amount without significantly increasing the complexity.

Furthermore, we can always treat each input example as an individual distribution, thus $\lambda$ is always zero. In this case, if we use batch size $B$ for $T$ iterations, we would have $l=N=BT$. Then our theorem indicate that as long as $m=\text{poly}(N,1/\delta^{\prime})$, where $\delta^{\prime}$ is the minimal distance between each examples, we can actually fit arbitrary labels of the input data. However, since the total iteration only depends on $\log m$, when $m=\text{poly}(N,1/\delta^{\prime})$ but the input data is actually structured (with small $k,l$ and large $\delta$), then SGD can actually achieve a small generalization error, even when the network has enough capacity to fit arbitrary labels of the training examples (and can also be done by SGD). Thus, we prove that SGD has a strong inductive bias on structured data: Instead of finding a bad global optima that can fit arbitrary labels, it actually finds those with good generalization guarantees. This gives more thorough explanation to the empirical observations in .

Intuition and Proof Sketch for A Simplified Case

To train a neural network with ReLU activations, there are two questions need to be addressed:

Why can SGD optimize the training loss? Or even finding a critical point? Since the underlying network is highly non-smooth, existing theorems do not give any finite convergence rate of SGD for training neural network with ReLUs activations.

Why can the trained network generalize? Even when the capacity is large enough to fit random labels of the input data? This is known as the inductive bias of SGD.

This work takes a step towards answering these two questions. We show that when the network is overparameterized, it becomes more “pseudo smooth”, which makes it easir for SGD to minimize the training loss, and furthermore, it will not hurt the generalization error. Our proof is based on the following important observation:

The more we overparameterize the network, the less likely the activation pattern for one neuron and one data point will change in a fixed number of iterations.

This observation allows us to couple the gradient of the true neural network with a “pseudo gradient” where the activation pattern for each data point and each neuron is fixed. That is, when computing the “pseudo gradient”, for fixed $r,i$, whether the $r$-th hidden node is activated on the $i$-th data point $x_{i}$ will always be the same for different $t$. (But for fixed $t$, for different $r$ or $i$, the sign can be different.) We are able to prove that unless the generalization error is small, the “pseudo gradient” will always be large. Moreover, we show that the network is actually smooth thus SGD can minimize the loss.

We then show that when the number $m$ of hidden neurons increases, with a properly decreasing learning rate, the total number of iterations it takes to minimize the loss is roughly not changed. However, the total number of iterations that we can couple the true gradient with the pseudo one increases. Thus, there is a polynomially large $m$ so that we can couple these two gradients until the network reaches a small generalization error.

Here we illustrate the proof sketch for a simplified case and Appendix A provides the proof. The proof for the general case is provided in Appendix B. In the simplified case, we further assume:

(No variance) Each $\mathcal{D}_{a,b}$ is a single data point $(x_{a,b},a)$, and also we are doing full batch gradient descent as opposite to the minibatch SGD.

Then we reload the loss notation as $L(w)=\sum_{a\in[k],b\in[l]}p_{a,b}L(w,x_{a,b},a),$ and the gradient is

Following the intuition above, we define the pseudo gradient as

where it uses $1_{\langle w^{(0)}_{r},x_{a,b}\rangle\geq 0}$ instead of $1_{\langle w_{r},x_{a,b}\rangle\geq 0}$ as in the true gradient. That is, the activation pattern is set to be that in the initialization. Intuitively, the pseudo gradient is similar to the gradient for a pseudo network $g$ (but not exactly the same), defined as $g_{i}(x,w):=\sum_{r=1}^{m}a_{i,r}\langle w_{r},x\rangle 1_{\left\langle w_{r}^{(0)},x\right\rangle\geq 0}.$ Coupling the gradients is then similar to coupling the networks $f$ and $g$.

For simplicity, let $v_{a,a,b}:=\sum_{i\not=a}o_{i}(x_{a,b},w)=\frac{\sum_{i\not=a}e^{f_{i}(x_{a,b},w)}}{\sum_{i=1}^{k}e^{f_{i}(x_{a,b},w)}}$ and when $s\neq a$, $v_{s,a,b}:=-o_{s}(x_{a,b},w)=-\frac{e^{f_{s}(x_{a,b},w)}}{\sum_{i=1}^{k}e^{f_{i}(x_{a,b},w)}}.$ Roughly, if $v_{a,a,b}$ is small, then $f_{a}(x_{a,b},w)$ is relatively larger compared to the other $f_{i}(x_{a,b},w)$, so the classification error is small.

We prove the following two main lemmas. The first says that at each iteration, the total number of hidden units whose gradient can be coupled with the pseudo one is quite large.

The second lemma says that the pseudo gradient is large unless the error is small.

Discussion of Insights from the Analysis

Our analysis, though for learning two-layer networks on well structured data, also sheds some light upon learning neural networks in more general settings.

Generalization. Several lines of recent work explain the generalization phenomenon of overparameterized networks by low complexity of the learned networks, from the point views of spectrally-normalized margins , compression , and PAC-Bayes .

Our analysis has partially explained how SGD (with proper random initialization) on structured data leads to the low complexity from the compression and PCA-Bayes point views. We have shown that in a neighborhood of the random initialization, w.h.p. the gradients are similar to those of another benign learning process, and thus SGD can reduce the error and reach a good solution while still in the neighborhood. The closeness to the initialization then means the weights (or more precisely the difference between the learned weights and the initialization) can be easily compressed. In fact, empirical observations have been made and connected to generalization in . Furthermore, explicitly point out such a compression using a helper string (corresponding to the initialization in our setting). also point out that the compression view can be regarded as a more explicit form of the PAC-Bayes view, and thus our intuition also applies to the latter.

The existence of a solution of a small generalization error near the initialization is itself not obvious. Intuitively, on structured data, the updates are structured signals spread out across the weights of the hidden neurons. Then for prediction, the random initialized part in the weights has strong cancellation, while the structured signal part in the weights collectively affects the output. Therefore, the latter can be much smaller than the former while the network can still give accurate predictions. In other words, there can be a solution not far from the initialization with high probability.

Some insight is provided on the low rank of the weights. More precisely, when the data are well clustered around a few patterns, the accumulated updates (difference between the learned weights and the initialization) should be approximately low rank, which can be seen from checking the SGD updates. However, when the difference is small compared to the initialization, the spectrum of the final weight matrix is dominated by that of the initialization and thus will tend to closer to that of a random matrix. Again, such observations/intuitions have been made in the literature and connected to compression and generalization (e.g., ).

Effect of random initialization. Our analysis also shows how proper random initializations helps the optimization and consequently generalization. Essentially, this guarantees that w.h.p. for weights close to the initialization, many hidden ReLU units will have the same activation patterns (i.e., activated or not) as for the initializations, which means the gradients in the neighborhood look like those when the hidden units have fixed activation patterns. This allows SGD makes progress when the loss is large, and eventually learns a good solution. We also note that it is essential to carefully set the scale of the initialization, which is a extensively studied topic . Our initialization has a scale related to the number of hidden units, which is particularly useful when the network size is varying, and thus can be of interest in such practical settings.

Experiments

This section aims at verifying some key implications: (1) the activation patterns of the hidden units couple with those at initialization; (2) The distance from the learned solution from the initialization is relatively small compared to the size of initialization; (3) The accumulated updates (i.e., the difference between the learned weight matrix and the initialization) have approximately low rank. These are indeed supported by the results on the synthetic and the MNIST data. Additional experiments are presented in Appendix D.

The network structure and the learning process follow those in Section 3; the number of hidden units $m$ varies in the experiments, and the weights are initialized with $\mathcal{N}(0,1/\sqrt{m})$. On the synthetic data, the SGD is run for $T=400$ steps with batch size $B=16$ and learning rate $\eta=10/m$. On MNIST, the SGD is run for $T=2\times 10^{4}$ steps with batch size $B=64$ and learning rate $\eta=4\times 10^{2}/m$.

Besides the test accuracy, we report three quantities corresponding to the three observations/implications to be verified. First, for coupling, we compute the fraction of hidden units whose activation pattern changed compared to the time at initialization. Here, the activation pattern is defined as $1$ if the input to the ReLU is positive and otherwise. Second, for distance, we compute the relative ratio $\|w^{(t)}-w^{(0)}\|_{F}/\|w^{(0)}\|_{F}$, where $w^{(t)}$ is the weight matrix at time $t$. Finally, for the rank of the accumulated updates, we plot the singular values of $w^{(T)}-w^{(0)}$ where $T$ is the final step. All experiments are repeated 5 times, and the mean and standard deviation are reported.

Results. Figure 1 shows the results on the synthetic data. The test accuracy quickly converges to $100\%$, which is even more significant with larger number of hidden units, showing that the overparameterization helps the optimization and generalization. Recall that our analysis shows that for a learning rate linearly decreasing with the number of hidden nodes $m$, the number of iterations to get the accuracy to achieve a desired accuracy should be roughly the same, which is also verified here. The activation pattern difference ratio is less than $0.1$, indicating a strong coupling. The relative distance is less than $0.1$, so the final solution is indeed close to the initialization. Finally, the top 20 singular values of the accumulated updates are much larger than the rest while the spectrum of the weight matrix do not have such structure, which is also consistent with our analysis.

Figure 2 shows the results on MNIST. The observation in general is similar to those on the synthetic data (though less significant), and also the observed trend become more evident with more overparameterization. Some additional results (e.g., varying the variance of the synthetic data) are provided in the appendix that also support our theory.

Conclusion

Acknowledgements

We would like to thank the anonymous reviewers of NeurIPS’18 and Jason Lee for helpful comments. This work was supported in part by FA9550-18-1-0166, NSF grants CCF-1527371, DMS-1317308, Simons Investigator Award, Simons Collaboration Grant, and ONR-N00014-16-1-2329. Yingyu Liang would also like to acknowledge that support for this research was provided by the Office of the Vice Chancellor for Research and Graduate Education at the University of Wisconsin Madison with funding from the Wisconsin Alumni Research Foundation.

References

Appendix A Proofs for the Simplified Case

In the simplified case, we make the following simplifying assumption:

(No variance) Each $\mathcal{D}_{a,b}$ is a single data point $(x_{a,b},a)$, and also we are doing full batch gradient descent as opposite to the minibatch SGD.

Recall that the loss is then $L(w)=\sum_{a\in[k],b\in[l]}p_{a,b}L(w,x_{a,b},a).$ The gradient descent update on $w$ is given by

where $o_{y}(x,w)=\frac{e^{f_{y}(x,w)}}{\sum_{i=1}^{k}e^{f_{i}(x,w)}}$. The pseudo gradient is defined as

When clear from the context, we write $v_{s,a,b}(w)$ as $v_{s,a,b}$. Then we can simplify the above expression as:

Furthermore, $v_{a,a,b}$ indicates the “classification error”. The smaller $v_{a,a,b}$ is, the smaller the classification error is.

In the following subsections, we first show that the gradient is coupled with the pseudo gradient, then show that if the classification error is large then the pseudo gradient is large, and finally prove the convergence.

which implies that $\left\|w^{(t)}_{r}-w^{(0)}_{r}\right\|_{2}\leq L\eta t$.

Now, for every $\tau\geq 0$, we consider the set $\mathcal{H}$ such that

For every $r\in\mathcal{H}$ and every $t\leq\frac{\tau}{2L\eta}$, we know that for every $a\in[k],b\in[l]$:

Now, we need to bound the size of $\mathcal{H}$. Since $\left\langle w_{r}^{(0)},x_{a,b}\right\rangle\sim\mathcal{N}(0,\sigma^{2})$, by standard property of Gaussian we directly have that for $|\mathcal{H}|\geq 1-\frac{e\tau kl}{\sigma}$. ∎

A.2 Error Large ⟹\implies Gradient Large

The pseudo gradient can be rewritten as the following summation:

We would like to show that if some $p_{a,b}v_{i,a,b}$ is large, a good fraction of $r\in[m]$ will have large pseudo gradient. Now, the first step is to show that for any fixed $\{p_{a,b}v_{i,a,b}\}$ (that does not depend on the random initialization $w^{(0)}_{r}$), with good probability (over the random choice of $w_{r}^{(0)}$) we have that $P_{i,r}$ is large; see Lemma A.2. Then we will take a union bound over an epsilon net on $\{p_{a,b}v_{i,a,b}\}$ to show that for every $\{p_{a,b}v_{,ia,b}\}$ (that can depend on $w_{r}^{(0)}$), at least a good fraction of of $P_{i,r}$ is large; See Lemma A.3.

For any possible fixed $\{p_{a,b}v_{1,a,b}\}_{a\in[k],b\in[l]}\in[-v,v]$ such that $p_{1,1}v_{1,1,1}=v$, we have:

where $\beta\bot x_{1,1}$. For every $\tau\geq 0$, consider the event $\mathcal{E}_{\tau}$ defined as

for all $a\in[k]\backslash,b\in[l]$: $\left|\left\langle\beta,x_{a,b}\right\rangle\right|\geq 4\tau$.

By the definition of initialization $w_{r}^{(0)}$, we know that:

By assumption we know that for every $a\in[k]\backslash,b\in[l]$:

Thus if we pick $\tau\leq\frac{\delta\sigma}{16ekl}$, taking a union bound we know that

Moreover, since $\Pr[\left|\alpha\right|\leq\tau]\geq\frac{\tau}{e\sigma}$ and $\alpha$ is independent of $\beta$, we know that $\Pr[\mathcal{E}_{\tau}]\geq\frac{\tau}{16e^{2}\sigma}$.

The following proof will conditional on this event $\mathcal{E}_{\tau}$, and then treat $\beta$ as fixed and let $\alpha$ be the only random variable. In this way, we will have: for every $\alpha$ such that $|\alpha|\leq\tau$ and for every $a\in[k]\backslash,b\in[l]$, since $|\langle\beta,x_{a,b}\rangle|\geq 4\tau$ and $|\alpha\langle x_{1,1},x_{a,b}\rangle|\leq\tau$,

which is a linear function of $\alpha$. With this information, we can rewrite $h\left(w_{r}^{(0)}\right)$ as:

where $p_{1,b}v_{1,1,b}\geq 0$ and $\textsf{Linear}(\alpha)$ is some linear function in $\alpha$. Thus, we know that

is a convex function with $\left|\partial_{\max}\phi(0)-\partial_{\min}\phi(0)\right|\geq v$. Then applying Lemma A.5 gives

Since for $\tau\leq\frac{\delta\sigma}{16ekl}$, conditional on $\mathcal{E}_{\tau}$ the density $p(\alpha)\in\left[\frac{1}{e\tau},\frac{e}{\tau}\right]$, which implies that

Now we can look at $P_{1,r}$. By the random initialization of $w_{r}^{(0)}$, and since by our assumption $v_{1,a,b},x_{a,b}$ are not functions of $w_{r}^{(0)}$, a standard tail bound of Gaussian random variables shows that for every fixed $v_{1,a,b}$ and every $c>10$:

Taking $c=100\sqrt{\log\frac{kl}{\delta\sigma}}$ and putting together with inequality (2) with $\tau=\Theta\left(\frac{\delta\sigma}{kl}\right)$ complete the proof. ∎

Now, we can take an epsilon net and switch the order of the quantifiers in Lemma A.2 as shown in the following lemma.

This lemma implies that if the classification error is large, then many $w_{r}$ will have a large gradient.

We first consider fixed $\{p_{a,b}v_{i,a,b}\}_{i,a\in[k],b\in[l]}\in[-v,v]$. First of all, using the randomness of $a_{i,r}$ we know that with probability at least $1/e$,

A.3 Convergence

Having the lemmas, we can now prove the convergence:

Thus, this lemma shows that eventually $v^{(t)}$ will be small. However, we do not give any bound on how small the step size $\eta$ needs to be, and how a small $v^{(t)}$ leads to a small classification error. These are addressed in the proof of the general case in the next section, but here we are content with an eventually small $v^{(t)}$ for a sufficiently small $\eta$.

By Lemma A.3, we know that there are at least $\Omega\left(\frac{\delta}{kl}\right)$ fraction of $r\in[m]$ such that

Now combine with Lemma A.1. If we pick $\tau=O\left(\frac{\sigma\delta}{k^{2}l^{2}}\right)$, then at least $\Omega\left(\frac{\delta}{kl}\right)$ fraction of $r\in[m]$ have

Thus, for a sufficiently small $\eta$, we have:

A.4 Technical Lemmas

The following lemma above non-smooth convex function v.s. linear function is needed in the proof.

We have for every $\tau\geq 0$, for every linear function $l(\alpha)$:

Without loss of generality (up to subtracting a linear function on $\phi$), let us assume that $\phi(0)=0$ and $l(\alpha)=-b$.

Moreover, denote $\rho=\partial_{\max}\phi(0)-\partial_{\min}\phi(0)\geq 0$, we know that at least one of the following is true:

$\partial_{\max}\phi(0)\geq\frac{\rho}{2}$,

$\partial_{\min}\phi(0)\leq-\frac{\rho}{2}$.

We shall give the proof for the case $\partial_{\max}\phi(0)\geq\frac{\rho}{2}$. The other case follows from replacing $\phi$ with $-\phi$.

Let us then consider the following two cases.

$b>0$, in this case, by convexity of $\phi(\alpha)$ we have that $\forall\alpha>0:\phi(\alpha)>0$. Thus,

$b<0$, in this case, $\phi(\alpha)$ intersects with at a point $\alpha_{0}\geq 0$. Consider two cases:

$\alpha_{0}\geq\frac{\tau}{2}$, then we have: $b\leq-\frac{\rho\tau}{4}$. Thus,

$\alpha_{0}\leq\frac{\tau}{2}$, then we have:

This completes the proof of the first claim. For the second claim, in case 1, we know that every $\alpha\in[\tau/2,\tau]$ would have $|\phi(\alpha)-l(\alpha)|\geq\frac{\tau\rho}{128}$. In case 2(a), every $\alpha\in[0,\alpha_{0}-\tau/4]$ satisfies this claim. In case 2(b) we can take every $\alpha\in[\alpha_{0}+\tau/4,\tau]$. This completes the proof. ∎

Appendix B Proofs for the General Case

We consider a minibatch SGD of batch size $B$, number of iterations $T=N/B$ and learning rate $\eta$ as the following process: Randomly divide the total training examples into $T$ batches, each of size $B$. Let the indices of the examples in the $t$-th batch be $\mathcal{B}_{t}$. The update rule is:

The pseudo gradient on a point $(x_{s},y_{s})$ is defined as:

In the following subsections, we first show that the gradient is coupled with the pseudo gradient, then show that if the classification error is large then the pseudo gradient is large, and finally prove the convergence.

We have the following lemma for coupling, analog to Lemma A.1.

B.2 Expected Error Large ⟹\implies Gradient Large

Following the same structure as before, we can write the expected pseudo gradient as:

where $v_{s,a,b}(x_{a,b},w)$ is defined as:

When clear from the context, we use $v_{s,a,b}(x_{a,b})$ for short. When the choice of $x_{a,b}$ is not important, we will also use $v_{s,a,b}$.

The proof is very similar to the proof of Lemma A.2.

where $\beta\bot x_{1,1}^{*}$. For every $\tau\geq 0$, consider the event $\mathcal{E}_{\tau}$ defined as

By the definition of initialization $w_{r}^{(0)}$, we know that:

By assumption we can simply calculate that for every $a\in[k]\backslash,b\in[l]$: $1-\langle x_{a,b}^{*},x_{1,1}^{*}\rangle^{2}\geq\delta^{2}$. This implies that

With $\tau=\frac{\sigma\delta}{12l}$, we know that $\Pr[\mathcal{E}_{\tau}]=\Omega\left(\frac{\tau}{\sigma}\right)$. The following proof will conditional on this event $\mathcal{E}_{\tau}$, and then treat $\beta$ as fixed and let $\alpha$ be the only random variable. In this way, for every $\alpha$ such that $|\alpha|\leq\tau$ and for every $a\in[k]\backslash,b\in[l]$:

is a linear function for $\alpha\in[-\tau,\tau]$ with probability $\geq 2/3$.

With this information, we can rewrite $h\left(w_{r}^{(0)}\right)$ as:

where $l(\alpha)$ is a convex function with $\partial_{\max}l(\tau)-\partial_{\max}l(-\tau)\leq v/3$.

We will have $\partial_{\max}\phi(\tau/2)-\partial_{\max}\phi(-\tau/2)\geq v/2$. Now apply Lemma B.5, we can conclude from the same proof of Lemma A.2. ∎

Now we can take the union bound to switch the order of quantifiers. However, we cannot do a naive union bound since there are infinitely many $x_{a,b}$. Instead, we will use a sampling trick to prove the following Lemma:

This lemma implies that if the classification error is large, then many $w_{r}$’s have a large pseudo gradient.

We first pick $S$ samples $\mathcal{S}=\{x_{a,b}^{(s)}\}$, with $p_{a,b}S$ many from distribution $\mathcal{D}_{a,b}$, and with the corresponding value function $v_{i,a,b}^{(s)}$. Since each $v_{i,a,b}^{(s)}\in$, we know that w.h.p., for every $i\in[k],a\in[k],b\in[l]$:

B.3 Convergence

We now show the following important lemma about convergence.

We know that for at least $\gamma$ fraction of $r\in[m]$ such that

Now we consider the non-smooth gradient descent. Consider a newly sampled point $(x^{\prime},y^{\prime})$, and let us denote

Let $G_{1}$ denote the event that (3) holds.

Theorem 4.1. Suppose the assumptions (A1)(A2)(A3) are satisfied. Then for every $\varepsilon>0$, there is $M=\text{poly}(k,l,1/\delta,1/\varepsilon)$ such that for every $m\geq M$, after doing a minibatch SGD with batch size $B=\text{poly}(k,l,1/\delta,1/\varepsilon,\log m)$ and learning rate $\eta=\frac{1}{m\cdot\text{poly}(k,l,1/\delta,1/\varepsilon,\log m)}$ for $T=\text{poly}(k,l,1/\delta,1/\varepsilon,\log m)$ iterations, with high probability:

Let $v_{i,a,b}^{(t)}$ denote $v_{i,a,b}(x_{a,b},w^{(t)})$.

Then for every $\varepsilon\leq\frac{1}{e}$, if $v^{(t)}_{a,a,b}(x_{a,b},w^{(t)})\leq\varepsilon$, then

$p_{a,b}\leq\frac{\varepsilon}{2kl}$. For all such $a,b$, even if all the predictions are wrong, it will only increase the total error by $\varepsilon/2$ so the other half $\varepsilon/2$ error must come from other $p_{a,b}$.

Therefore, to prove the theorem, it suffices to show that $v^{(t)}$ will be smaller than $\frac{\varepsilon^{3}}{8kl}$ after a proper amount of iterations. Suppose $v^{(t)}\geq\frac{\varepsilon^{3}}{8kl}$, then by Lemma B.4, as long as

B.4 Technical Lemmas

The following lemma above non-smooth convex function v.s. linear function is needed in the proof.

We have that for every $\tau\geq 0$, for every convex function $l(\alpha)$, let $\gamma=(\partial_{\max}\phi(\tau/2)-\partial_{\min}\phi(-\tau/2))-(\partial_{\max}l(\tau)-\partial_{\min}l(-\tau))$, then

Without loss of generality, we can assume that either $\partial_{\max}l(\tau)$ and $\partial_{\max}\phi(\tau/2)\geq\gamma/2$ , or $\partial_{\min}l(-\tau)=0$ and $\partial_{\min}\phi(-\tau/2)\leq-\gamma/2$. The lemma can be proved using the same argument as in Lemma A.5. ∎

We also need the following lemma regarding the gradient descent on non-smooth function.

The proof of this lemma follows directly from

where the last line follows from the chain rule and Lipschitz smoothness, and the last to second line follows from

Appendix C Illustration of the Separability Assumption

(Separability) There exists $\delta>0$ such that for every $i_{1}\not=i_{2}\in[k]$ and every $j_{1},j_{2}\in[l]$,

Appendix D Additional Experimental Results

Here we provide some additional experimental results.

Recall that our analysis that for a learning rate decreasing with the number of hidden nodes $m$, the number of iterations to get the accuracy roughly remain the same. A more direct way to check is to plot the number of steps to achieve the accuracy for different $m$. As shown in Figure 4, the number of steps roughly match what our theory predicts.

Furthermore, Figure 5 shows the relative distances when achieving the desired accuracies. It is observed that the distances scale roughly as $O(1/\sqrt{m})$. In particular, they closely match $2/3\sqrt{m}$ on the synthetic data and $8/\sqrt{m}$ on MNIST (the red lines in the figures), where $m$ is the number of hidden nodes. Explanations are left for future work.

D.2 Synthetic Data with Larger Variances

Figure 6 shows that the test accuracy decreases with increasing variance $\sigma$, and it takes longer time to get a good solution. On the other hand, an increasing variance does not change the trends for activation patterns, distance, and the rank of the weight matrix. This is possibly due to that the signal in the updates remain small with increasing variances, while the noise in the updates act similarly as the randomness in the weights.

D.3 Synthetic Data with Larger Number of Components in Each Class