Convergence and Generalization of Wide Neural Networks with Large Bias
This work studies training one-hidden-layer overparameterized ReLU networks
via gradient descent in the neural tangent kernel (NTK) regime, where the
networks' biases are initialized to some constant rather than zero. The
tantalizing benefit of such initialization is that the neural network will
provably have sparse activation through the entire training process, which
enables fast training procedures. The first set of results characterizes the
convergence of gradient descent training. Surprisingly, it is shown that the
network after sparsification can achieve as fast convergence as the dense
network, in comparison to the previous work indicating that the sparse networks
converge slower. Further, the required width is improved to ensure gradient
descent can drive the training error towards zero at a linear rate. Secondly,
the networks' generalization is studied: a width-sparsity dependence is
provided which yields a sparsity-dependent Rademacher complexity and
generalization bound. To our knowledge, this is the first sparsity-dependent
generalization result via Rademacher complexity. Lastly, this work further
studies the least eigenvalue of the limiting NTK. Surprisingly, while it is not
shown that trainable biases are necessary, trainable bias, which is enabled by
our improved analysis scheme, helps to identify a nice data-dependent region
where a much finer analysis of the NTK's smallest eigenvalue can be conducted.
This leads to a much sharper lower bound on the NTK's smallest eigenvalue than
the one previously known and, consequently, an improved generalization bound.
Hongru Yang, Ziyu Jiang, Ruizhe Zhang, Zhangyang Wang, Yingbin Liang
# Convergence and Generalization of Wide Neural Networks with Large Bias

###### Abstract

This work studies training one-hidden-layer overparameterized ReLU networks via gradient descent in the neural tangent kernel (NTK) regime, where the networks' biases are initialized to some constant rather than zero. The tantalizing benefit of such initialization is that the neural network will provably have sparse activation through the entire training process, which enables fast training procedures. The first set of results characterizes the convergence of gradient descent training. Surprisingly, it is shown that the network after sparsification can achieve as fast convergence as the dense network, in comparison to the previous work indicating that the sparse networks converge slower. Further, the required width is improved to ensure gradient descent can drive the training error towards zero at a linear rate. Secondly, the networks' generalization is studied: a width-sparsity dependence is provided which yields a sparsity-dependent Rademacher complexity and generalization bound. To our knowledge, this is the first sparsity-dependent generalization result via Rademacher complexity. Lastly, this work further studies the least eigenvalue of the limiting NTK. Surprisingly, while it is not shown that trainable biases are necessary, trainable bias, which is enabled by our improved analysis scheme, helps to identify a nice data-dependent region where a much finer analysis of the NTK's smallest eigenvalue can be conducted. This leads to a much sharper lower bound on the NTK's smallest eigenvalue than the one previously known and, consequently, an improved generalization bound.

## 1 Introduction

The literature of sparse neural networks can be dated back to the early work of LeCun et al. (1989) where they showed that a fully-trained neural network can be pruned to preserve generalization. Recently, training sparse neural networks has been receiving increasing attention since the discovery of the lottery ticket hypothesis (Frankle and Carbin, 2018). In their work, they showed that if we repeatedly train and prune a neural network and then rewind the weights to the initialization, we are able to find a sparse neural network that can be trained to match the performance of its dense counterpart. However, this method is more of a proof of concept and is computationally expensive for any practical purposes. Nonetheless, this inspires further interest in the machine learning community to develop efficient methods to find the sparse pattern at the initialization such that the performance of the sparse network can match the dense network after training (Lee
et al., 2018; Wang et al., 2019; Tanaka et al., 2020; Liu and Zenke, 2020; Chen et al., 2021; He et al., 2017; Liu et al., 2021b).

On the other hand, instead of trying to find some desirable sparsity patterns at the initialization, another line of research has been focusing on inducing the sparsity pattern naturally and then cleverly utilizing such sparse structure via techniques like high-dimensional geometric data structures, sketching or even quantum algorithms to speedup per-step gradient descent training (Song et al., 2021a, b; Hu et al., 2022; Gao et al., 2022). In this line of theoretical studies, the sparsity is induced by shifted ReLU which is the same as initializing the bias of the network's linear layer to some large constant instead of zero and holding the bias fixed throughout the entire training. By the concentration of Gaussian, at the initialization, the total number of activated neurons (i.e., ReLU will output some non-zero value) will be _sublinear_ in the total number \(m\) of neurons, as long as the bias is initialized to be \(C\sqrt{\log m}\) for some appropriate constant \(C\). We call this _sparsity-inducing initialization_. If the network is in the NTK regime, each neuron weight will exhibit microscopic change after training, and thus the sparsity can be preserved throughout the entire training process. Therefore, during the entire training process, only a sublinear number of the neuron weights need to be updated, which can significantly speedup the training process.

The focus of this work is along the above line of theoretical studies of sparsely activated overparameterized neural networks and address the two main research limitations in the aforementioned studies: (1) prior work indicates that the sparse networks have **slower convergence guarantee** than the dense network, despite that the per step gradient descent training can be made cheaper and (2) the previous works only provided the convergence guarantee, while **lacking the generalization analysis** which is of central interest in deep learning theory. Thus, our study will fill the above important gaps, by providing a comprehensive study of training one-hidden-layer sparsely activated neural networks in the NTK regime with (a) finer analysis of the convergence; and (b) first generalization bound for such sparsely activated neural networks after training with sharp bound on the restricted smallest eigenvalue of the limiting NTK. We further elaborate our technical contributions are follows:

1. **Convergence.** Surprisingly, Theorem 3.1 shows that the network after sparsification can achieve as fast convergence as the original network. This is made possible by the fact that the sparse networks allow a much more relaxed condition on the learning rate, which was not discovered in the previous work. The theorem further provides an improved required width to ensure that gradient descent can drive the training error towards zero at a linear rate. At the core of our convergence result is a finer analysis where the required network width to ensure convergence is made much smaller, with an improvement upon the previous result by a factor of \(\widetilde{\Theta}(n^{8/3})\) under appropriate bias initialization, where \(n\) is the sample size. This relies on our novel development of (1) a better characterization of the activation flipping probability via an analysis of the Gaussian anti-concentration based on the location of the strip and (2) a finer analysis of the initial training error.
2. **Generalization.** Theorem 3.8 studies the generalization of the network after gradient descent training where we characterize how the network width should depend on activation sparsity, which lead to a sparsity-dependent localized Rademacher complexity and generalization bound. When the sparsity parameter is set to zero (i.e., the activation is not sparsified), our bound matches previous analysis up to logarithmic factors. To our knowledge, this is the first sparsity-dependent generalization result via localized Rademacher complexity. In addition, compared with previous works, our result yields a better width's dependence by a factor of
\(n^{10}\). This relies on (1) the usage of symmetric initialization and (2) a finer analysis of the weight matrix change in Frobenius norm in Lemma 3.13.
3. **Restricted Smallest Eigenvalue.** Theorem 3.8 shows that the generalization bound heavily depends on the smallest eigenvalue \(\lambda_{\min}\) of the limiting NTK. However, the previously known worst-case lower bounds on \(\lambda_{\min}\) under data separation have a \(1/n^{2}\) explicit dependence in (Oymak and Soltanolkotabi, 2020; Song et al., 2021), making the generalization bound vacuous. Instead, we note that our improved convergence analysis in Theorem 3.1 can handle trainable bias. Relying on our new result that the change of bias is also diminishing with a \(O(1/\sqrt{m})\) dependence on the network width \(m\), we show that even though the biases are allowed to be updated by gradient descent, the network's activation remains sparse during the entire training. Based on that, our Theorem 3.11 establishes a much sharper lower bound restricted to a data-dependent region, which is sample-size-independent. This hence yields a worst-case generalization bound for _bounded_ loss of \(O(1)\) as opposed to \(O(n)\) in previous analysis, given that the label vector is in this region, which can be achieved with simple label-shifting.

### Further Related Works

Besides the works mentioned in the introduction, another work related to ours is (Liao and Kyrillidis, 2022) where they also considered training a one-hidden-layer neural network with sparse activation and studied its convergence. However, different from our work, their sparsity is induced by sampling a random mask at each step of gradient descent whereas our sparsity is induced by non-zero initialization of the bias terms. Also, their network has no bias term, and they only focus on studying the training convergence but not generalization. We discuss additional related works here.

**Training Overparameterized Neural Networks.** Over the past few years, a tremendous amount of efforts have been made to study training overparameterized neural networks. A series of works have shown that if the neural network is wide enough (polynomial in depth, number of samples, etc), gradient descent can drive the training error towards zero in a fast rate either explicitly (Du et al., 2018, 2019; Ji and Telgarsky, 2019) or implicitly (Allen-Zhu et al., 2019; Zou and Gu, 2019; Zou et al., 2020) using the neural tangent kernel (NTK) (Jacot et al., 2018). Further, under some conditions, the networks can generalize (Cao and Gu, 2019). Under the NTK regime, the trained neural network can be well-approximated by its first order Taylor approximation from the initialization and Liu et al. (2020) showed that this transition to linearity phenomenon is a result from a diminishing Hessian 2-norm with respect to width. Later on, Frei and Gu (2021) and Liu et al. (2022) showed that closeness to initialization is sufficient but not necessary for gradient descent to achieve fast convergence as long as the non-linear system satisfies some variants of the Polyak-Lojasiewicz condition. On the other hand, although NTK offers good convergence explanation, it contradicts the practice since (1) the neural networks need to be unrealistically wide and (2) the neuron weights merely change from the initialization. As Chizat et al. (2019) pointed out, this "lazy training" regime can be explained by a mere effect of scaling. To go beyond NTK, there are other works considering the mean-field limit (Chizat and Bach, 2018; Mei et al., 2019; Chen et al., 2020), and feature learning (Allen-Zhu and Li, 2020, 2022; Shi et al., 2021; Telgarsky, 2022).
**Sparse Neural Networks in Practice.** Besides finding a fixed sparse mask at the initialization as we mentioned in introduction, on the other hand, dynamic sparse training allows the sparse mask to be updated during training, e.g., (Mocanu et al., 2018; Mostafa and Wang, 2019; Evci et al., 2020; Jayakumar et al., 2020; Liu et al., 2021a,c,d).

## 2 Preliminaries

**Notations.** We use \(\left\lVert\cdot\right\rVert_{2}\) to denote vector or matrix 2-norm and \(\left\lVert\cdot\right\rVert_{F}\) to denote the Frobenius norm of a matrix. When the subscript of \(\left\lVert\cdot\right\rVert\) is unspecified, it is default to be the 2-norm. For matrices \(A\in\mathbb{R}^{m\times n_{1}}\) and \(B\in\mathbb{R}^{m\times n_{2}}\), we use \([A,B]\) to denote the row concatenation of \(A,B\) and thus \([A,B]\) is a \(m\times(n_{1}+n_{2})\) matrix. For matrix \(X\in\mathbb{R}^{m\times n}\), the row-wise vectorization of \(X\) is denoted by \(\vec{X}=[x_{1},x_{2},\ldots,x_{m}]^{\top}\) where \(x_{i}\) is the \(i\)-th row of \(X\). For a given integer \(n\in\mathbb{N}\), we use \([n]\) to denote the set \(\{0,\ldots,n\}\), i.e., the set of integers from \(0\) to \(n\). For a set \(S\), we use \(\overline{S}\) to denote the complement of \(S\). We use \(\mathcal{N}(\mu,\sigma^{2})\) to denote the Gaussian distribution with mean \(\mu\) and standard deviation \(\sigma\). In addition, we use \(\widetilde{O},\widetilde{\Theta},\widetilde{\Omega}\) to suppress (poly-)logarithmic factors in \(O,\Theta,\Omega\).

### Problem Formulation

Let the training set to be \((X,y)\) where \(X=(x_{1},x_{2},\ldots,x_{n})\in\mathbb{R}^{d\times n}\) denotes the feature matrix consisting of \(n\)\(d\)-dimensional vectors, and \(y=(y_{1},y_{2},\ldots,y_{n})\in\mathbb{R}^{n}\) consists of the corresponding \(n\) response variables. We assume \(\left\lVert x_{i}\right\rVert_{2}\leq 1\) and \(y_{i}=O(1)\) for all \(i\in[n]\). We use one-hidden-layer neural network and consider the regression problem with the square loss function:

\[f(x;W,b) :=\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(\langle w_{r},x \rangle-b_{r}),\] \[L(W,b) :=\frac{1}{2}\sum_{i=1}^{n}(f(x_{i};W,b)-y_{i})^{2},\]

where \(W\in\mathbb{R}^{m\times d}\) with its \(r\)-th row being \(w_{r}\), \(b\in\mathbb{R}^{m}\) is a vector with \(b_{r}\) being the bias of \(r\)-th neuron, \(a_{r}\) is the second layer weight, and \(\sigma(\cdot)\) denotes the ReLU activation function. We initialize the neural network by \(W_{r,i}\sim\mathcal{N}(0,1)\) and \(a_{r}\sim\text{Uniform}(\{\pm 1\})\) and \(b_{r}=B\) for some value \(B\geq 0\) of choice, for all \(r\in[m],\ i\in[d]\). We train only the parameters \(W\) and \(b\) via gradient descent (i.e., with the linear layer \(a_{r},\ r\in[m]\) fixed), the updates are given by

\[[w_{r},b_{r}](t+1)=[w_{r},b_{r}](t)-\eta\frac{\partial L(W(t),b(t))}{\partial[w_ {r},b_{r}]}.\]

By the chain rule, we have \(\frac{\partial L}{\partial w_{r}}=\frac{\partial L}{\partial f}\frac{ \partial f}{\partial w_{r}}\). The gradient of the loss with respect to the network is \(\frac{\partial L}{\partial f}=\sum_{i=1}^{n}(f(x_{i};W,b)-y_{i})\) and the network gradients with respect to weights and bias are

\[\frac{\partial f(x;W,b)}{\partial w_{r}} =\frac{1}{\sqrt{m}}a_{r}\mathbb{I}(w_{r}^{\top}x\geq b_{r}),\] \[\frac{\partial f(x;W,b)}{\partial b_{r}} =-\frac{1}{\sqrt{m}}a_{r}\mathbb{I}(w_{r}^{\top}x\geq b_{r}),\]
where \(\mathbb{I}(\cdot)\) is the indicator function. We use the shorthand \(\mathbb{I}_{r,i}:=\mathbb{I}(w_{r}^{\top}x_{i}\geq b_{r})\) and we define the **NTK** matrix \(H\) as

\[H_{i,j}(W,b) :=\left\langle\frac{\partial f(x_{i};W,b)}{\partial[W,b]},\frac{ \partial f(x_{j};W,b)}{\partial[W,b]}\right\rangle \tag{2.1}\] \[=\frac{1}{m}\sum_{r=1}^{m}(\langle x_{i},x_{j}\rangle+1)\mathbb{I }_{r,i}\mathbb{I}_{r,j},\]

and the **infinite-width version**\(H^{\infty}(B)\) of the NTK matrix \(H\) is given by

\[H_{ij}^{\infty}(B):=\operatorname*{\mathbb{E}}_{w}\left[(\langle x_{i},x_{j} \rangle+1)\mathbb{I}(w^{\top}x_{i}\geq B,w^{\top}x_{j}\geq B)\right].\]

Let \(\lambda(B):=\lambda_{\min}(H^{\infty}(B))\). We define the matrix \(Z(W,b)\in\mathbb{R}^{m(d+1)\times n}\) as

\[Z(W,b):=\frac{1}{\sqrt{m}}\begin{bmatrix}\mathbb{I}_{1,1}a_{1}\widetilde{x}_ {1}&\ldots&\mathbb{I}_{1,n}a_{1}\widetilde{x}_{n}\\ \vdots&\ddots&\vdots\\ \mathbb{I}_{m,1}a_{m}\widetilde{x}_{1}&\ldots&\mathbb{I}_{m,n}a_{m}\widetilde{ x}_{n}\end{bmatrix},\]

where \(\widetilde{x}_{i}:=[x_{i}^{\top},-1]^{\top}\). Note that \(H(W,b)=Z(W,b)^{\top}Z(W,b)\). Hence, the gradient descent step can be written as

\[[W,b](\vec{t}+1)=[W,\vec{b}](t)-\eta Z(t)(f(t)-y),\]

where \([W,b](t)\in\mathbb{R}^{m\times(d+1)}\) denotes the row-wise concatenation of \(W(t)\) and \(b(t)\) at the \(t\)-th step of gradient descent, and \(Z(t):=Z(W(t),b(t))\).

## 3 Main Theory

### Convergence and Sparsity

We first present the convergence of gradient descent for the sparsely activated neural networks. Surprisingly, we show that the sparse network can achieve as fast convergence as the dense network compared to the previous work (Song et al., 2021) which, on the other hand, shows the sparse networks converge slower than the dense networks.

**Theorem 3.1** (Convergence).: _Let the learning rate \(\eta\leq O(\frac{\lambda(B)\exp(B^{2})}{n^{2}})\), and the bias initialization \(B\in[0,\sqrt{0.5\log m}]\). Assume \(\lambda(B)=\lambda_{0}\exp(-B^{2}/2)\) for some \(\lambda_{0}>0\) independent of \(B\). Then, if the network width satisfies \(m\geq\widetilde{\Omega}\left(\lambda_{0}^{-4}n^{4}\exp(B^{2})\right)\), with probability at least \(1-\delta-e^{-\Omega(n)}\) over the randomness in the initialization,_

\[\forall t:L(W(t),b(t))\leq(1-\eta\lambda(B)/4)^{t}L(W(0),b(0)).\]

The assumption on \(\lambda(B)\) in Theorem 3.1 can be justified by (Song et al., 2021, Theorem F.1) which shows that under some mild conditions, the NTK's least eigenvalue \(\lambda(B)\) is positive and has an \(\exp(-B^{2}/2)\) dependence. Given this, Theorem 3.1 in fact implies that the convergence rate is _independent_ of the sparsity parameter due to the extra \(\exp(B^{2})\) term in the learning rate. This means that the network with sparse activation can achieve as fast convergence as the original network. Our study further handles trainable bias (with constant initialization). This is done by a
new result in Lemma A.9 that the change of bias is also diminishing with a \(O(1/\sqrt{m})\) dependence on the network width \(m\).

**Remark 3.2**.: _Theorem 3.1 establishes a much sharper bound on the width of the neural network than previous work to guarantee the linear convergence. To elaborate, our bound only requires \(m\geq\widetilde{\Omega}\left(\lambda_{0}^{-4}n^{4}\exp(B^{2})\right)\), as opposed to the bound \(m\geq\widetilde{\Omega}(\lambda_{0}^{-4}n^{4}B^{2}\exp(2B^{2}))\) in (Song et al., 2021a, Lemma D.9). If we take \(B=\sqrt{0.25\log m}\) (as allowed by the theorem), then our lower bound yields a polynomial improvement by a factor of \(\widetilde{\Theta}(n/\lambda_{0})^{8/3}\), which implies that the neural network width can be much smaller to achieve the same linear convergence._

**Key results in the proof of Theorem 3.1.** The proof mainly consists of a novel analysis on activation flipping probability and a finer upper bound on initial error, as we elaborate.

Like previous works, in order to prove convergence, we need to show that the NTK during training is close to its initialization. Inspecting the expression of NTK in Equation (2.1), observe that the training will affect the NTK by changing the output of each indicator function. We say that the \(r\)-th neuron flips its activation with respect to input \(x_{i}\) at the \(k\)-th step of gradient descent if \(\mathbb{I}(w_{r}(k)^{\top}x_{i}-b_{r}(k)>0)\neq\mathbb{I}(w_{r}(k-1)^{\top}x_{ i}-b_{r}(k-1)>0)\) for all \(r\in[m]\). The central idea is that for each neuron, as long as the weight and bias movement \(R_{w},R_{b}\) from its initialization is small, then the probability of activation flipping (with respect to random initialization) should not be large. We first present the bound on the probability that a neuron flips its activation.

**Lemma 3.3** (Bound on Activation flipping probability).: _Let \(B\geq 0\) and \(R_{w},R_{b}\leq\min\{1/B,1\}\). Let \(\widetilde{W}=(\widetilde{w}_{1},\ldots,\widetilde{w}_{m})\) be vectors generated i.i.d. from \(\mathcal{N}(0,I)\) and \(\widetilde{b}=(\widetilde{b}_{1},\ldots,\widetilde{b}_{m})=(B,\ldots,B)\), and weights \(W=(w_{1},\ldots,w_{m})\) and biases \(b=(b_{1},\ldots,b_{m})\) that satisfy for any \(r\in[m]\), \(\left\|\widetilde{w}_{r}-w_{r}\right\|_{2}\leq R_{w}\) and \(\widetilde{b}_{r}-b_{r}|\leq R_{b}\). Define the event_

\[A_{i,r}=\{\exists w_{r},b_{r}:\left\|\widetilde{w}_{r}-w_{r} \right\|_{2}\leq R_{w},\ |b_{r}-\widetilde{b}_{r}|\leq R_{b},\] \[\mathbb{I}(x_{i}^{\top}\widetilde{w}_{r}\geq\widetilde{b}_{r}) \neq\mathbb{I}(x_{i}^{\top}w_{r}\geq b_{r})\}.\]

_Then, for some constant \(c\),_

\[\mathbb{P}\left[A_{i,r}\right]\leq c(R_{w}+R_{b})\exp(-B^{2}/2).\]

(Song et al., 2021a, Claim C.11) presents a \(O(\min\{R,\exp(-B^{2}/2)\})\) bound on \(\mathbb{P}[A_{i,r}]\). The reason that their bound involving the min operation is because \(\mathbb{P}[A_{i,r}]\) can be bounded by the standard Gaussian tail bound and Gaussian anti-concentration bound separately and then, take the one that is smaller. On the other hand, our bound replaces the min operation by the product which creates a more convenient (and tighter) interpolation between the two bounds. Later, we will show that the maximum movement of neuron weights and biases, \(R_{w}\) and \(R_{b}\), both have a \(O(1/\sqrt{m})\) dependence on the network width, and thus our bound offers a \(\exp(-B^{2}/2)\) improvement where \(\exp(-B^{2}/2)\) can be as small as \(1/m^{1/4}\) when we take \(B=\sqrt{0.5\log m}\).

**Proof idea of Lemma 3.3.** First notice that \(\mathbb{P}[A_{i,r}]=\mathbb{P}_{x\sim\mathcal{N}(0,1)}[|x-B|\leq R_{w}+R_{b}]\). Thus, here we are trying to solve a fine-grained Gaussian anti-concentration problem with the strip centered at \(B\). The problem with the standard Gaussian anti-concentration bound is that it only provides a worst case bound and, thus, is location-oblivious. Centered in our proof is a nice Gaussian anti-concentration bound based on the location of the strip, which we describe as follows: Let's first assume \(B>R_{w}+R_{b}\). A simple probability argument yields a bound of
\(2(R_{w}+R_{b})\frac{1}{\sqrt{2\pi}}\exp(-(B-R_{w}-R_{b})^{2})\). Since later in the Appendix we can show that \(R_{w}\) and \(R_{b}\) have a \(O(1/\sqrt{m})\) dependence (Lemma A.9 bounds the movement for gradient descent and Lemma A.10 for gradient flow) and we only take \(B=O(\sqrt{\log m})\), by making \(m\) sufficiently large, we can safely assume that \(R_{w}\) and \(R_{b}\) is sufficiently small. Thus, the probability can be bounded by \(O((R_{w}+R_{b})\exp(-B^{2}/2))\). However, when \(B<R_{w}+R_{b}\) the above bound no longer holds. But a closer look tells us that in this case \(B\) is close to zero, and thus \((R_{w}+R_{b})\frac{1}{\sqrt{2\pi}}\exp(-B^{2}/2)\approx\frac{R_{w}+R_{b}}{ \sqrt{2\pi}}\) which yields roughly the same bound as the standard Gaussian anti-concentration.

Next, our analysis develops the following initial error bound.

**Lemma 3.4** (Initial error upper bound).: _Let \(B>0\) be the initialization value of the biases and all the weights be initialized from standard Gaussian. Let \(\delta\in(0,1)\) be the failure probability. Then, with probability at least \(1-\delta\) over the randomness in the initialization, we have_

\[L(0)=O\left(n+n\left(\exp(-\frac{B^{2}}{2})+\frac{1}{m}\right)\log^{3}(\frac{ 2mn}{\delta})\right).\]

(Song et al., 2021, Claim D.1) gives a rough estimate of the initial error with \(O(n(1+B^{2})\log^{2}(n/\delta)\log(m/\delta))\) bound. When we set \(B=C\sqrt{\log m}\) for some constant \(C\), our bound improves the previous result by a polylogarithmic factor. The previous bound is not tight in the following two senses: (1) the bias will only decrease the magnitude of the neuron activation instead of increasing and (2) when the bias is initialized as \(B\), only roughly \(O(\exp(-B^{2}/2))\cdot m\) neurons will activate. Thus, we can improve the \(B^{2}\) dependence to \(\exp(-B^{2}/2)\).

By combining the above two improved results, we can prove our convergence result with improved lower bound of \(m\) as in Remark 3.2. To relax the condition on the learning rate for the sparse network, a finer analysis of the error terms is conducted in Lemma A.17 by leveraging the fact that the network has sparse activation. This later translates into a wider range of learning rate choice in the convergence analysis. We provide the complete proof in Appendix A.

Lastly, since the total movement of each neuron's bias has a \(O(1/\sqrt{m})\) dependence (shown in Lemma A.9), combining with the number of activated neurons at the initialization, we can show that during the entire training, the number of activated neurons is small.

**Lemma 3.5** (Number of Activated Neurons per Iteration).: _Assume the parameter settings in Theorem 3.1. With probability at least \(1-e^{-\Omega(n)}\) over the random initialization,_

\[|\mathcal{S}_{\mathrm{on}}(i,t)|=O(m\cdot\exp(-B^{2}/2))\]

_for all \(0\leq t\leq T\) and \(i\in[n]\), where \(\mathcal{S}_{\mathrm{on}}(i,t)=\{r\in[m]:\ w_{r}(t)^{\top}x_{i}\geq b_{r}(t)\}\)._

### Generalization and Restricted Least Eigenvalue

In this section, we present our sparsity-dependent generalization result. For technical reasons stated in Section 3.3, we use symmetric initialization defined below. Further, we adopt the setting in (Arora et al., 2019) and use a non-degenerate data distribution to make sure the infinite-width NTK is positive definite.

**Definition 3.6** (Symmetric Initialization).: _For a one-hidden layer neural network with \(2m\) neurons, the network is initialized as the following:_

1. _For_ \(r\in[m]\)_, independently initialize_ \(w_{r}\sim\mathcal{N}(0,I)\) _and_ \(a_{r}\sim\mathrm{Uniform}(\{-1,1\})\)_._
_._
2. _For_ \(r\in\{m+1,\ldots,2m\}\)_, let_ \(w_{r}=w_{r-m}\) _and_ \(a_{r}=-a_{r-m}\)_._

**Definition 3.7** (\((\lambda_{0},\delta,n)\)-non-degenerate distribution, (Arora et al., 2019)).: _A distribution \(\mathcal{D}\) over \(\mathbb{R}^{d}\times\mathbb{R}\) is \((\lambda_{0},\delta,n)\)-non-degenerate, if for \(n\) i.i.d. samples \(\{(x_{i},y_{i})\}_{i=1}^{n}\) from \(\mathcal{D}\), with probability \(1-\delta\) we have \(\lambda_{\min}(H^{\infty}(B))\geq\lambda_{0}>0\)._

**Theorem 3.8**.: _Fix a failure probability \(\delta\in(0,1)\) and an accuracy parameter \(\epsilon\in(0,1)\). Suppose the training data \(S=\{(x_{i},y_{i})\}_{i=1}^{n}\) are i.i.d. samples from a \((\lambda,\delta,n)\)-non-degenerate distribution \(\mathcal{D}\) defined in Definition 3.7. Assume the one-hidden layer neural network is initialized by symmetric initialization in Definition 3.6. Further, assume the parameter settings in Theorem 3.1 except we let \(m\geq\widetilde{\Omega}\left(\lambda(B)^{-6}n^{6}\exp(-B^{2})\right)\). Consider any loss function \(\ell:\mathbb{R}\times\mathbb{R}\rightarrow[0,1]\) that is \(1\)-Lipschitz in its first argument. Then with probability at least \(1-2\delta-e^{-\Omega(n)}\) over the randomness in symmetric initialization of \(W(0)\in\mathbb{R}^{m\times d}\) and \(a\in\mathbb{R}^{m}\) and the training samples, the two layer neural network \(f(W(t),b(t),a)\) trained by gradient descent for \(t\geq\Omega(\frac{1}{n\lambda(B)}\log\frac{n\log(1/\delta)}{\epsilon})\) iterations has empirical Rademacher complexity (see its formal definition in Definition C.1 in Appendix) bounded as_

\[\mathcal{R}_{S}(\mathcal{F})\] \[\leq\sqrt{\frac{y^{\top}(H^{\infty}(B))^{-1}y\cdot 8e^{-B^{2}/2}}{n }}+\widetilde{O}\left(\frac{e^{-B^{2}/4}}{n^{1/2}}\right)\]

_and the population loss \(L_{\mathcal{D}}(f)=\mathbb{E}_{(x,y)\sim\mathcal{D}}[\ell(f(x),y)]\) can be upper bounded as_

\[L_{\mathcal{D}}(f(W(t),b(t),a)) \tag{3.1}\] \[\leq\sqrt{\frac{y^{\top}(H^{\infty}(B))^{-1}y\cdot 32e^{-B^{2}/2}}{n }}+\widetilde{O}\left(\frac{1}{n^{1/2}}\right).\]

To show good generalization, we need a larger width: the second term in the Rademacher complexity bound is diminishing with \(m\) and to make this term \(O(1/\sqrt{n})\), the width needs to have \((n/\lambda(B))^{6}\) dependence as opposed to \((n/\lambda(B))^{4}\) for convergence. Now, at the first glance of our generalization result, it seems we can make the Rademacher complexity arbitrarily small by increasing \(B\). Recall from the discussion of Theorem 3.1 that the smallest eigenvalue of \(H^{\infty}(B)\) also has an \(\exp(-B^{2}/2)\) dependence. Thus, in the worst case, the \(\exp(-B^{2}/2)\) factor gets canceled and sparsity will not hurt the network's generalization.

Before we present the proof, we make a corollary of Theorem 3.8 for the zero-initialized bias case.

**Corollary 3.9**.: _Take the same setting as in Theorem 3.8 except now the biases are initialized as zero, i.e., \(B=0\). Then, if we let \(m\geq\widetilde{\Omega}(\lambda(0)^{-6}n^{6})\), the empirical Rademacher complexity and population loss are both bounded by_

\[\mathcal{R}_{S}(\mathcal{F}),\ L_{\mathcal{D}}(f(W(t),b(t),a))\] \[\leq\sqrt{\frac{y^{\top}(H^{\infty}(0))^{-1}y\cdot 32}{n}}+ \widetilde{O}\left(\frac{1}{n^{1/2}}\right).\]

Corollary 3.9 requires the network width \(m\geq\widetilde{\Omega}((n/\lambda(0))^{6})\) which significantly improves upon the previous result in (Song and Yang, 2019, Theorem G.7) \(m\geq\widetilde{\Omega}(n^{16}\operatorname{poly}(1/\lambda(0)))\) (including the dependence on the rescaling factor \(\kappa\)) which is a much wider network.
**Generalization Bound via Least Eigenvalue.** Note that in Theorem 3.8, the worst case of the first term in the generalization bound in Equation (3.1) is given by \(\widetilde{O}(\sqrt{1/\lambda(B)})\). Hence, the least eigenvalue \(\lambda(B)\) of the NTK matrix can significantly affect the generalization bound. Previous works (Oymak and Soltanolkotabi, 2020; Song et al., 2021) established lower bounds on \(\lambda(B)\) with an explicit \(1/n^{2}\) dependence on \(n\) under the \(\delta\) data separation assumption (see Theorem 3.11), which clearly makes a vacuous generalization bound of \(\widetilde{O}(n)\). This thus motivates us to provide a tighter bound (desirably independent on \(n\)) on the least eigenvalue of the infinite-width NTK in order to make the generalization bound in Theorem 3.8 valid and useful. It turns out that there are major difficulties in proving a better lower bound in the general case. However, we are only able to present a better lower bound when we restrict the domain to some (data-dependent) regions by utilizing trainable bias.

**Definition 3.10** (Data-dependent Region).: _Let \(p_{ij}=\mathbb{P}_{w\sim\mathcal{N}(0,I)}[w^{\top}x_{i}\geq B,\ w^{\top}x_{j} \geq B]\) for \(i\neq j\). Define the (data-dependent) region \(\mathcal{R}=\{a\in\mathbb{R}^{n}:\ \sum_{i\neq j}a_{i}a_{j}p_{ij}\geq\min_{i^{ \prime}\neq j^{\prime}}p_{i^{\prime}j^{\prime}}\sum_{i\neq j}a_{i}a_{j}\}.\)_

Notice that \(\mathcal{R}\) is non-empty for any input data-set since \(\mathbb{R}^{n}_{+}\subset\mathcal{R}\) where \(\mathbb{R}^{n}_{+}\) denotes the set of vectors with non-negative entries, and \(\mathcal{R}=\mathbb{R}^{n}\) if \(p_{ij}=p_{i^{\prime}j^{\prime}}\) for all \(i\neq i^{\prime},j\neq j^{\prime}\).

**Theorem 3.11** (Restricted Least Eigenvalue).: _Let \(X=(x_{1},\ldots,x_{n})\) be points in \(\mathbb{R}^{d}\) with \(\left\|x_{i}\right\|_{2}=1\) for all \(i\in[n]\) and \(w\sim\mathcal{N}(0,I_{d})\). Suppose that there exists \(\delta\in[0,\sqrt{2}]\) such that_

\[\min_{i\neq j\in[n]}(\left\|x_{i}-x_{j}\right\|_{2},\left\|x_{i}+x_{j}\right\| _{2})\geq\delta.\]

_Let \(B\geq 0\). Consider the minimal eigenvalue of \(H^{\infty}\) over the data-dependent region \(\mathcal{R}\) defined above, i.e., let \(\lambda:=\min_{\left\|a\right\|_{2}=1,\ a\in\mathcal{R}}a^{\top}H^{\infty}a\). Then, \(\lambda\geq\max(0,\lambda^{\prime})\) where_

\[\lambda^{\prime} \geq\max\left(\frac{1}{2}-\frac{B}{\sqrt{2\pi}},\ \left(\frac{1}{B}-\frac{1}{B^{3}}\right)\frac{e^{-B^{2}/2}}{\sqrt{2\pi}}\right)\] \[-e^{-B^{2}/(2-\delta^{2}/2)}\frac{\pi-\arctan\left(\frac{\delta \sqrt{1-\delta^{2}/4}}{1-\delta^{2}/2}\right)}{2\pi}. \tag{3.2}\]

To demonstrate the usefulness of our result, if we take the bias initialization \(B=0\) in Equation (3.2), this bound yields \(1/(2\pi)\cdot\arctan((\delta\sqrt{1-\delta^{2}/4})/(1-\delta^{2}/2))\approx \delta/(2\pi)\), when \(\delta\) is close to \(0\) whereas (Song et al., 2021) yields a bound of \(\delta/n^{2}\). On the other hand, if the data has maximal separation, i.e., \(\delta=\sqrt{2}\), we get a \(\max\left(\frac{1}{2}-\frac{B}{\sqrt{2\pi}},\ \left(\frac{1}{B}-\frac{1}{B^{3}}\right)\frac{e^{-B^{2}/2}}{\sqrt{2\pi}}\right)\) lower bound, whereas (Song et al., 2021) yields a bound of \(\exp(-B^{2}/2)\sqrt{2}/n^{2}\). Connecting to our convergence result in Theorem 3.1, if \(f(t)-y\in\mathcal{R}\), then the error can be reduced at a much faster rate than the (pessimistic) rate with \(1/n^{2}\) dependence in the previous studies as long as the error vector lies in the region.

**Remark 3.12**.: _The lower bound on the restricted smallest eigenvalue \(\lambda\) in Theorem 3.11 is_ **independent of \(n\)**_, which makes that the worst case generalization bound in Theorem 3.8 be \(O(1)\) under constant data separation margin (note that this is optimal since the loss is bounded). Such a lower bound is much sharper than the previous results with a \(1/n^{2}\) explicit dependence which yields vacuous generalization bound of \(O(n)\). This improvement relies on the condition that the label vector should lie in the region \(\mathcal{R}\), which can be achieved by a simple label-shifting strategy:_
_Since \(\mathbb{R}_{+}^{n}\subset\mathcal{R}\), the condition can be easily achieved by training the neural network on the shifted labels \(y+C\) (with appropriate broadcast) where \(C\) is a constant such that \(\min_{i}y_{i}+C\geq 0\)._

Careful readers may notice that in the proof of Theorem 3.11 in Appendix B, the restricted least eigenvalue on \(\mathbb{R}_{+}^{n}\) is always positive even if the data separation is zero, which would imply that the network can always exhibit good generalization. However, we need to point out that the generalization bound in Theorem 3.8 is meaningful only when the training is successful: when the data separation is zero, the limiting NTK is no longer positive definite and the training loss cannot be minimized toward zero.

### Key Ideas in the Proof of Theorem 3.8

Since each neuron weight and bias move little from their initialization, a natural approach is to bound the generalization via localized Rademacher complexity. After that, we can apply appropriate concentration bounds to derive generalization. The main effort of our proof is devoted to bounding the weight movement to bound the localized Rademacher complexity. If we directly take the setting in Theorem 3.1 and compute the network's localized Rademacher complexity, we will encounter a non-diminishing (with the number of samples \(n\)) term which can be as large as \(O(\sqrt{n})\) since the network outputs non-zero values at the initialization. Arora et al. (2019) and Song and Yang (2019) resolved this issue by initializing the neural network weights instead by \(\mathcal{N}(0,\kappa^{2}I)\) to force the neural network output something close to zero at the initialization. The magnitude of \(\kappa\) is chosen to balance different terms in the Rademacher complexity bound in the end. Similar approach can also be adapted to our case by initializing the weights by \(\mathcal{N}(0,\kappa^{2}I)\) and the biases by \(\kappa B\). However, the drawback of such an approach is that the effect of \(\kappa\) to all the previously established results for convergence need to be carefully tracked or derived. In particular, in order to guarantee convergence, the neural network's width needs to have a polynomial dependence on \(1/\kappa\) where \(1/\kappa\) has a polynomial dependence on \(n\) and \(1/\lambda\), which means their network width needs to be larger to compensate for the initialization scaling. We resolve this issue by symmetric initialization Definition 3.6 which yields no effect (up to constant factors) on previously established convergence results, see (Munteanu et al., 2022). Symmetric initialization allows us to organically combine the results derived for convergence to be reused for generalization, which leads to a more succinct analysis. Further, we replace the \(\ell_{1}\)-\(\ell_{2}\) norm upper bound by finer inequalities in various places in the original analysis. All these improvements lead to the following upper bound of the weight matrix change in Frobenius norm. Further, combining our sparsity-inducing initialization, we present our sparsity-dependent Frobenius norm bound on the weight matrix change.

**Lemma 3.13**.: _Assume the one-hidden layer neural network is initialized by symmetric initialization in Definition 3.6. Further, assume the parameter settings in Theorem 3.1. Then with probability at least \(1-\delta-e^{-\Omega(n)}\) over the random initialization, we have for all \(t\geq 0\),_

\[\left\|[W,b](t)-[W,b](0)\right\|_{F}\] \[\leq\sqrt{y^{\top}(H^{\infty})^{-1}y}+O\left(\frac{n}{\lambda} \left(\frac{\exp(-B^{2}/2)\log(n/\delta)}{m}\right)^{\frac{1}{4}}\right)\] \[\quad+O\left(\frac{n\sqrt{R\exp(-B^{2}/2)}}{\lambda}\right)\]
\[+\frac{n}{\lambda^{2}}\cdot O\left(\exp(-B^{2}/4)\sqrt{\frac{\log(n^{2 }/\delta)}{m}}+R\exp(-B^{2}/2)\right)\]

_where \(R=R_{w}+R_{b}\) denote the maximum magnitude of neuron weight and bias change._

By Lemma A.9 and Lemma A.11 in the Appendix, we have \(R=\widetilde{O}(\frac{n}{\lambda\sqrt{m}})\). Plugging in and setting \(B=0\), we get \(\left\|[W,b](t)-[W,b](0)\right\|_{F}\leq\sqrt{y^{\top}(H^{\infty})^{-1}y}+ \widetilde{O}(\frac{n}{\lambda m^{1/4}}+\frac{n^{3/2}}{\lambda^{3/2}m^{1/4}}+ \frac{n}{\lambda^{2}\sqrt{m}}+\frac{n^{2}}{\lambda^{3}\sqrt{m}})\). On the other hand, taking \(\kappa=1\), (Song and Yang, 2019, Lemma G.6) yields a bound of \(\left\|W(t)-W(0)\right\|_{F}\leq\sqrt{y^{\top}(H^{\infty})^{-1}y}+\widetilde{ O}(\frac{n}{\lambda}+\frac{n^{7/2}\operatorname{poly}(1/\lambda)}{m^{1/4}})\). Notice that the \(\widetilde{O}(\frac{n}{\lambda})\) term has no dependence on \(1/m\) and is removed by symmetric initialization in our analysis. We further improve the upper bound's dependence on \(n\) by a factor of \(n^{2}\).

The full proof of Theorem 3.8 is deferred in Appendix C.

### Key Ideas in the Proof of Theorem 3.11

In this section, we analyze the smallest eigenvalue of the limiting NTK \(H^{\infty}\) with \(\delta\) data separation. We first note that \(H^{\infty}\succeq\mathbb{E}_{w\sim\mathcal{N}(0,I)}\left[\mathbb{I}(Xw\geq B) \mathbb{I}(Xw\geq B)^{\top}\right]\) and for a fixed vector \(a\), we are interested in the lower bound of \(\mathbb{E}_{w\sim\mathcal{N}(0,I)}[\|a^{\top}\mathbb{I}(Xw\geq B)|^{2}]\). In previous works, Oymak and Soltanolkotabi (2020) showed a lower bound \(\Omega(\delta/n^{2})\) for zero-initialized bias, and later Song et al. (2021a) generalized this result to a lower bound \(\Omega(e^{-B^{2}/2}\delta/n^{2})\) for non-zero initialized bias. Both lower bounds have a dependence of \(1/n^{2}\). Their approach is by using an intricate Markov's inequality argument and then proving an lower bound of \(\mathbb{P}[|a^{\top}\mathbb{I}(Xw\geq B)|\geq c\left\|a\right\|_{\infty}]\). The lower bound is proved by only considering the contribution from the largest coordinate of \(a\) and treating all other values as noise. It is non-surprising that the lower bound has a factor of \(1/n\) since \(a\) can have identical entries. On the other hand, the diagonal entries can give a \(\exp(-B^{2}/2)\) upper bound and thus there is a \(1/n^{2}\) gap between the two. Now, we give some evidence suggesting the \(1/n^{2}\) dependence may not be tight in some cases. Consider the following scenario: Assume \(n\ll d\) and the data set is orthonormal. For any unit-norm vector \(a\), we have

\[a^{\top}\mathop{\mathbb{E}}_{w\sim\mathcal{N}(0,I)}\left[\mathbb{ I}(Xw\geq B)\mathbb{I}(Xw\geq B)^{\top}\right]a\] \[=\sum_{i,j\in[n]}a_{i}a_{j}\,\mathbb{P}[w^{\top}x_{i}\geq B,\ w^{ \top}x_{j}\geq B]\] \[=p_{0}\left\|a\right\|_{2}^{2}+p_{1}\sum_{i\neq j}a_{i}a_{j}\] \[=p_{0}-p_{1}+p_{1}\left(\sum_{i}a_{i}\right)^{2}>p_{0}-p_{1}\]

where \(p_{0},p_{1}\in[0,1]\) are defined such that due to the spherical symmetry of the standard Gaussian we are able to let \(p_{0}=\mathbb{P}[w^{\top}x_{i}\geq B],\ \forall i\in[n]\) and \(p_{1}=\mathbb{P}[w^{\top}x_{i}\geq B,w^{\top}x_{j}\geq B],\ \forall i,j\in[n],\ i\neq j\). Notice that \(p_{0}>p_{1}\). Since this is true for all \(a\in\mathbb{R}^{n}\), we get a lower bound of \(p_{0}-p_{1}\) with no explicit dependence on \(n\) and this holds for all \(n\leq d\). When \(d\) is large and \(n=d/2\), this bound is better than previous bound by a factor of \(\Theta(1/d^{2})\). We hope to apply the above analysis to general datasets. However, it turns out that the product terms (with \(i\neq j\)) above creates major difficulties in the general case. Due to such technical difficulties, we prove a better lower bound by utilizing the data-dependent region \(\mathcal{R}\) defined in Definition 3.10. Let \(p_{\min}=\min_{i\neq j}p_{ij}\). Now, for \(a\in\mathcal{R}\), we
have

\[\mathop{\mathbb{E}}_{w\sim\mathcal{N}(0,I)}\left[\left(a^{\top} \mathbb{I}(Xw\geq B)\right)^{2}\right]\] \[\geq\left(p_{0}-p_{\min}\right)\left\|a\right\|_{2}^{2}+p_{\min} \left\|a\right\|_{2}^{2}+p_{\min}\sum_{i\neq j}a_{i}a_{j}\] \[\geq\left(p_{0}-\min_{i\neq j}p_{ij}\right)\left\|a\right\|_{2}^{ 2}.\]

Thus, to lower bound the smallest eigenvalue on this region, we need to get an upper bound on \(\min_{i\neq j}p_{ij}\). To do this, let's first consider a fixed pair of training data \(x_{i}\) and \(x_{j}\) and their associated probability \(p_{ij}\) (see Definition 3.10). To compute \(p_{ij}\), we can decompose \(x_{j}\) into two components: one is along the direction of \(x_{i}\) and the other is orthogonal to \(x_{i}\). Now we can project the Gaussian vector onto these two directions and since the two directions are orthogonal, they are independent. This allows \(p_{ij}\) to be computed via geometry arguments. It turns out that this probability is maximized when the data separation is the smallest. We defer the details of the proof of Theorem 3.11 to Appendix B.

## 4 Experiments

In this section, we verify our result that the activation of neural networks remains sparse during training when the bias parameters are initialized as non-zero.

**Settings.** We train a 6-layer multi-layer perceptron (MLP) of width 1024 with trainable bias terms on MNIST image classification (LeCun et al., 2010). The biases of the fully-connected layers are initialized as \(0,-0.5\) and \(-1\). For the weights in the linear layer, we use Kaiming Initialization (He et al., 2015) which is sampled from an appropriately scaled Gaussian distribution. The traditional MLP architecture only has linear layers with ReLU activation. However, we found out that using the sparsity-inducing initialization, the magnitude of the activation will decrease geometrically layer-by-layer, which leads to vanishing gradients and that the network cannot be trained. Thus, we made a slight modification to the MLP architecture to include an extra Batch

Figure 1: Sparsity pattern on different layers across different training iterations for three different bias initialization. The \(x\) and \(y\) axis denote the iteration number and sparsity level, respectively. The models can achieve \(97.9\%,97.7\%\) and \(97.3\%\) accuracy after training, respectively. Note that, in Figure (a), the lines of layers 1-5 overlap together except layer 0.
Normalization after ReLU to normalize the activation. Our MLP implementation is based on (Zhu et al., 2021). We train the neural network by stochastic gradient descent with a small learning rate 5e-3 to make sure the training is in the NTK regime. The sparsity is measured as the total number of activated neurons (i.e., ReLU outputs some positive values) divided by total number of neurons, averaged over every SGD batch. We plot how the sparsity patterns changes for different layers during training.

**Observation and Implication.** As demonstrated at Figure 1, when we initialize the bias with three different values, the sparsity patterns are stable across all layers during training: when the bias is initialized as \(0\) and \(-0.5\), the sparsity change is within \(2.5\%\); and when the bias is initialized as \(-1.0\), the sparsity change is within \(10\%\). Meanwhile, by increasing the initialization magnitude for bias, the sparsity level increases with only marginal accuracy dropping. This implies that our theory can be extended to the multi-layer setting (with some extra care for coping with vanishing gradient) and multi-layer neural networks can also benefit from the sparsity-inducing initialization and enjoy reduction of computational cost. Another interesting observation is that the input layer (layer 0) has a different sparsity pattern from other layers while all the rest layers behave similarly.

## 5 Discussion

In this work, we study training one-hidden-layer overparameterized ReLU networks in the NTK regime where its biases initialized as some constants rather than zero so that its activation remains sparse during the entire training process. We showed an improved sparsity-dependent results on convergence, generalization and restricted least eigenvalue. One immediate future direction is to generalize our analysis to multi-layer neural networks. On the other hand, in practice, label shifting is never used. Although we show that the least eigenvalue can be much better than previous result when we impose additional assumption of the restricted region, an open problem is whether it is possible to improve the infinite-width NTK's least eigenvalue's dependence on the sample size without such assumption, or even whether a lower bound purely dependent on the data separation is possible so that the worst-case generalization bound doesn't scale with the sample size. We leave them as future work.
