Sharper Analysis of Sparsely Activated Wide Neural Networks with Trainable Biases
Authors: Hongru Yang
Ziyu Jiang
Ruizhe Zhang
Zhangyang Wang
Yingbin Liang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Convergence analysis
sparse activation
neural tangent kernel
Rademacher complexity
generalization bound

Abstract: This work studies training one-hidden-layer overparameterized ReLU networks via gradient descent in the neural tangent kernel (NTK) regime, where, differently from the previous works, the networks' biases are trainable and are initialized to some constant rather than zero. The tantalizing benefit of such initialization is that the neural network will provably have sparse activation pattern before, during and after training, which can enable fast training procedures and, therefore, reduce the training cost. The first set of results of this work characterize the convergence of the network's gradient descent dynamics. The required width is provided to ensure gradient descent can drive the training error towards zero in linear rate. The contribution over previous work is that not only the bias is allowed to be updated by gradient descent under our setting but also a finer analysis is given such that the required width to ensure the network's closeness to its NTK is improved. Secondly, the networks' generalization bound after training is provided. A width-sparsity dependence is presented which yields sparsity-dependent localized Rademacher complexity and same-as-previous (ignoring logarithmic factors) generalization bound. Up to our knowledge, this is the first sparsity-dependent generalization result via localized Rademacher complexity. As a by-product, if the bias initialization is chosen to be zero, the width requirement improves the previous bound for the shallow networks' generalization. Lastly, since the generalization bound has dependence on the smallest eigenvalue of the limiting NTK and the bounds from previous works yield vacuous generalization, this work further studies the least eigenvalue of the limiting NTK. Surprisingly, while it is not shown that trainable biases are necessary, trainable bias helps to identify a nice data-dependent region where a much finer analysis of the NTK's smallest eigenvalue can be conducted, which leads to a much sharper lower bound than the previously known worst-case bound and, consequently, a non-vacuous generalization bound. Experimental evaluation is provided to evaluate our results. 

Under review as a conference paper at ICLR 2023
SHARPER ANALYSIS OF SPARSELY ACTIVATED WIDE NEURAL NETWORKS WITH TRAINABLE BIASES
Anonymous authors Paper under double-blind review
ABSTRACT
This work studies training onehiddeen-layer overparameterized ReLU networks via gradient descent in the neural tangent kernel (NTK) regime, where, differently from the previous works, the networks' biases are trainable and are initialized some constant rather than zero. The tantalizing benefit of such initialization is that the neural network will provably have sparse activation pattern before, during and after training, which can enable fast training procedures and, therefore, reduce the training cost. The first set of results of this work characterize the convergence the network's gradient descent dynamics. The required width is provided ensure gradient descent can drive the training error towards zero at a linear rate. The con- tribution over previous work is that not only the bias is allowed to be updated by gradient descent under our setting but also a finer analysis is given such that the re- quired width ensure the network's closeness to its NTK is improved. Secondly, the networks' generalization bound after training is provided. A width-sparsity dependence is presented which yields pparsity-dependeed localized Rademacher complexity and a generalization bound matching previous analysis (up to loga- rithmic factors). To our knowledge, this the first sparsity-dependent general- ization result via localized Rademacher complexity. As a by-product, if the bias initialization chosen to be zero, the width requirement improves the previous bound for the shallow networks' generalization. Lastly, since the generalization bound has dependence on the smallest eigenvalue of the limiting NTK and the bounds from previous works yield vacuous generalization, this work further stud- ies the least eigenvalue of the limiting NTK. Surprisingly, while it is not shown that trainable biases are necessary, trainable bias helps identify nice data- dependent region where a much finer analysis of the NTK's smallest eigenvalue can be conducted, which leads to a much sharper lower bound than the previously known worst-case bound and, consequently, a non-vacuous generalization bound. Experimental evaluation is provided evaluate our results.
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. Re- cently, training sparse neural networks has been receiving increasing attention since the discovery of the lottery ticket hypothesis (Frankle & Carbin 2018). In their work, they showed that if we repeat- edly train and prune a neural network and then rewind the weights the initialization, to find a sparse neural network that can be trained to match the performance of its dense counter- part. However, this method is more of 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 matches the dense network after training (Lee et al.) 2018 Wang et al. 2019 Tanaka et al. 2020 Liu & Zenke 2020 Chen et al. 2021 He et al. 2017 Liu et al. 202
are able
On the other hand, instead of trying to find some desired sparsity patterns at the initialization, another line of research has been focusing on inducing the sparsity pattern naturally and then creatively utilizing such sparse structure via nigh-dimensional geometric data structures well as sketching or even quantum algorithms to speedup per-step gradient descent training (Song et al.) [022aa Hu
et al. 2022
Gao al. 2022). In this line of theoretical studies, the sparsity is induced by shifted

---

Under review as a conference paper at ICLR 2023
ReLU which is the same 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 CVlog 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 trained overparame- terized neural networks and address the two main research limitations in the aforementioned studies. (1) The bias parameters used in the previous works are not trainable, contrary to what people are do- ing in practice. (2) The previous works only provided the convergence guarantee, while lacking the generalization performance which is of the 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) trainable biases incorporated in the analysis; (b) finer analysis of the convergence; and (c) 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. Theorem 3.1 provides the required width to ensure that gradient descent can drive the training error towards zero at a linear rate. Our convergence result contains two novel ingredients compared to the existing study. (1) Our analysis handles trainable bias, and shows that even though the biases are allowed to be updated from its initialization, the network's 's activation remains sparse during the entire training. This relies our develop- ment of new result showing that the change of bias is also diminishing with a O /m) dependence on the network width m. (2) A finer analysis is provided such that the required network width to ensure the convergence can be much smaller, with an improvement upon the previous result by factor of (n38/) 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 mnti-concentration based on the location of the strip and (2) finer analysis of the initial training error.
2. Generalization. Theorem 3.8 studies the generalization of the network after gradient de- scent training where we characterize how the network width should depend on activation sparsity, which lead to a deeeede-de localized Rademacher complexity and gener- alization bound matching previous analysis (up to logarithmic factors). To our knowledge, this is the first sparsity-dependent generalization result via localized Rademacher complex- ity. In addition, compared with previous works, our result yields a better width's is depen- dence by factor of n n0 This relies on (1) the usage of symmetric initialization and (2) 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 heav- ily depends on the smallest eigenvalue Amio of the limiting NTK. However, the previously known worst-case lower bounds on Amia under data separation have 1/n²² explicit depen- dence in (Oymak & Soltanolkotabi] 2020) [Song et al.) 2021a), making the generalization bound vacuous. Instead, our Theorem 3.11 establishes much sharper lower bound re- stricted to a data-dependent region, which is sample-size-indeeedder
This hence yields a desirable generalization bound that vanishes fast as ((1/vn), given that the label vector is in this region, which can be done with simple label-shifting.
1.1 FURTHER RELATED WORKS
Besides the works mentioned in the introduction, another work related to ours is (Liao & Kyrillidis) 2022) where they also considered training a one-hiddennlayer neural network with sparse activation and studied its convergence. However, different from our work, their sparsity is induced by sam- pling random mask at each step of gradient descent whereas 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.
2

---

Under review as a conference paper at ICLR 2023
Training Overparameterizee Neural Networks. Over the past few years, a tremendous amount of efforts have been made to study training overparameterized neural networks. 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 & Telgarsky 2019) implicitly (Allen-Zhu et al. 2019 Zou & Gu 20T9) (Zou al., 2020 using the neural tangent kernel (NTK) (Jacot et al. 2018). Further, under some conditions, the networks can generalize (Cao & 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 linearity phenomenon a result from a diminishing Hessian 2- norm with respect to width. Later on, Frei & Gu (2021) and et al. (2022) showed that closeness to initialization sufficient but not necessary for gradient descent to achieve fast convergence as condition. On the
long the non-linear system satisfies some variants of 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. Other works have considered the mean-field limit (Chizat & Bach 2018
Mei et al. 2019 Chen et al., 2020), feature learning (Allen-Zhu & Li 2020 2022 Shi et al. 2021 which allow the weights travel far away from the initialization.
Telgarsky 2022
Sparse Neural Networks in Practice. Besides finding 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 & Wang 2019
Evci et al. 2020
Jayakumar al. 2020 Liu al. 2021a
PRELIMINARIES
Notations. We use |l-I|2 to denote vector or matrix 2-norm and ||-I|r denote the Frobenius norm of a matrix. When the subscript of ||-I| is unspecified, it is default to be the 2-norm. For matrices A mmxm and B Rmxx,, we use [A, B] to denote the row concatenation of A, B and thus [A is m x (ni + n2)) matrix. For matrix X E IR=x", the row-wise vectorization of X is denoted by vec(X)
_m] where x; the i-th row of X. For a given integer n E N, we use [n] to denote the set (0, (O.....7) .n., i.e. the set of integers from 0 to n. For set S, we use 5 to denote the complement of S. We use N(,, a²) to denote the Gaussian distribution with mean μ and standard deviation a. In addition, we use O O 52 to suppress (poly-)oogarthmmie factors in O, Ω
[21, .2...... ................................ Zmm]
2.1 PROBLEM FORMULATION
Let the training set to be (X, y) where X = (I1, X2, ....... )nn E Rdx. denotes the feature matrix consisting of d-dimensional vectors, and y (y1 ....... Vnn E R" consists of the corresponding response variables. We assume ||æ:||| I 1 and = (1) 1) for all E [n]. We use one- one-hidden-layer neural network and consider the regression problem with the square loss function:
1 mm
f(r W,b) ==
a ((w,, br),
a
L(W, = 2 Σ
v:)?
where W& E md with its r-th row being Wr, b E Rm is a vector with b, being the bias of r-th neuron, a, is the second layer weight, and o-)) denotes the ReLU activation function. We initialize the neural network by W., ~ (N00 1) and a, ~ Uniform({ (1) and b, B for some value B 2 0 of choice, for r E [m], [d]. We train only the parameters W and (i.e., the linear layer a, for [m] is not trained) via gradient descent, the update of which are given by
w. w. (t+ (t) (L(WW(), b(t))
(L(W b(t))
1)
Ow,
ab
By the chain rule, we have AL aL as The gradient of the loss with respect to the network is du- af dw.
8f Ef W,b) - y:) and the network gradients with respect to weights and bias are
0f(x: W,b) 1 rww br),
0f W,b) 1 a, x 2 br),
Ow,
bb,
mm
3

---

Under review as a conference paper at ICLR 2023
where I(.) is the indicator function. We further define H the NTK matrix of this network with
(z W)b) af W.b) 0f(z W) 0f(a;; W,
Hig (W,
ow
oW
Ob
Øb
(1)) + 1), 21 2 br, W, Dj 2 br)
(I)
m
and the wndtnite-width version (B) of the NTK matrix H/ is given by Hi (B) == N(). [((2,, + 1)l(W T x; 2 B, w zj 2 B)
Let A(B) = Amin (0 (B)). We define (W, b) == I(w, x, 2 b,) and the matrix Z(W, b) as 11., (W. b)a [ 1]
I1,1 (W,,Wa) b -1]
Z(W,6) ;= mm
1
E R [m((+1)xx
I (W. b)am [xT, -1 I (W, 0m [.p _
Note that H(W,b) b)
Z(W, b) Z(W, b). Hence, the gradient descent step can be written as ve, 6] + 1)) vec((W,b](1)) - (f)()(((t) - y)
where [tt E mx((1++1 denotes the row-wise concatenation of (t) and b(t) at the t-th step of gradient descent, and Z(t) == Z (t),)
MAIN THEORY
3.1 CONVERGENCE AND SPARSITY
We present the convergence of gradient descent for the sparsely activated neural networks. Com- pared to the existing convergence result in (Song al. (021a), our study handles the trainable bias with constant initialization in the convergence analysis (which is the first of such a type). Also, our bound is sharper and yields much smaller bound the width of neural networks to guarantee the convergence.
Theorem 3.1 (Convergence). Let the learning rafe nj S O (eepp( and the bias initialization B E [0, 00. log m.) Assume X(B) Ag exp(-B²/2) for some Ao independent of B. Then, if the network width satisfies m 2 (>p *n exp(B3)). over the randomness in the initialization,
P Vt: (LW b()) I (1
L(W
2 -
- -9())
This theorem show that the training loss decreases linearly, and its rate depends on the smallest eigenvalue of the NTK. The assumption X(B) in Theorem 3.1 can be justified by (Song al., 2021a Theorem F.1) which shows that under some mild conditions, the NTK's least eigenvalue X(B) positive and has an exp(-B²)) /2) dependence.
Remark 3.2. Theorem 3.1 establishes a much sharper bound on the width the neural network than previous work guarantee the linear convergence. To elaborate,
bound only requires m 9 (A, exp (xp((²)). as opposed to the bound 2 5aAA, "n', B² exp(2B²)) in (Song al. 2021a Lemma D.9). If we take B 00.25 log m (as allowed by the theorem), then our lower bound yields a polynomial improvement by a factor network width can be much smaller achieve the same linear convergence.
88/3, which implics that the neural
The proof mainly consists of developing a novel bound on activation flipping probability and novel upper bound on initial error, we elaborate below.
Key ideas in the proof of Theorem 3.1
Like previous works, in order to prove convergence, we need to show that the NTK during training close to its initialization. Inspecting the expression of NTK in Equation (T). 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 2; at the k-th step of gradient descent if [[(,((k)
bkk > 0) # I(w, (k - 1) x; - by - 1) > 0) for all r E [m]. The central idea is that for each neuron, long as the weight and bias movement Rw, Rs 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 given neuron flips its activation.
4

---

Under review as a conference paper at ICLR 2023
Lemma 3.3 (Bound on Activation flipping probability). Let B 2 0 and Rw: Rs I min 1}. Let W = (.1.....: (m) be vectors generated i.i.d. from (N0, T) and b (b,,..,, .m) (B....,B) B), and weights W = -(W1,... Wm) and biases b = (b).... .ah.....baa bm) that satisfy for any r E [m], ||ū,, wrll2 I Rw and 1b, - byl S Rs. Define the event
Air = (3w,, by ||00, wrll2 - Rw: |b, b s Ro. [x, wr 2 b,) + I( w, 2 b.))
Then, for some constant e,
PP [Airr] S cBw + Ro) exp( (xxpp-B//2)
Song et al. 2021a Claim C.11) presents a O exp( (D2BBB2)) bound on r[..,r] The reason that their bound involving the min operation is because P[Ac.] 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 hetween the two bounds. Later, we will show that the maximum movement of neuron weights and biases, Rw and Rg, both have ((1vv dependence on the network width, and thus our bound offers a exp(-B2 (B) improvement where exp(- B2/2) /2) can be as small as 1/m2/4 when we take B = 0.5
Proof idea of Lemma 3.3 First notice that IP[A.r] P P==~N(0.1) B| S R. + Ra]. Thus, here we are trying to solve a fine-grained Gaussian anti-coneentratton problem with the strip centered at B. The problem with the standard Gaussian anti-concentration bound is that it only provides worst case bound and, thus, is location-obliviou.. Centered in our proof is a nice Gaussian anti- concentration bound based the location of the strip, which we describe as follows: Let's first assume B= > R Rs. A simple probability argument yields a bound of 2 R + +Ro) //= cxp(-(B-
Rw- Rs ))) Since later in the Appendix we can show that R., and Rs have O(1/ /m) dependence (Lemma A.9 bouods the movement for gradient descent and C.mma/A.10) for gradient flow) and we only take B OVIlo m) by making m sufficiently large, we can safely assume that R., and Rg is sufficiently small. Thus, the probability can be bounded by O( + Rs) exp(-B² (1-BB/2)) /2). However, when B- < R., + Rd the above bound no longer holds. But a closer look tells us that in this case B is close to zero, and thus ( (Rw + Rb) /2T exp(- (B22(BB2)))))) ~ bound as the standard Gaussian anti-concentration.
Rs which yields roughly the same V2n
Next, our proof of Theorem 3.1 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 E (0,1) 1) be the failure probability. Then, with probability at least 1 5 over the randomness in the initialization, we have
L(W ((0) = O (n + (exp(-B²/2 + 1/m) log log"((2m/00) (2mm/6)).
(Song et al., 2021a Claim D.I) gives rough estimate of the initial error with O(n(1 + lo) (n/ log (m/6)) bound. When we set Cvlog 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 ((exp((B2)))
m neurons
will activate. Thus, we can improve the B² dependence to exp(- B² /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 We provide the complete proof in Appendix A
Lastly, since the total movement of each neuron's 's bias has O(1/ 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 Theo- rem 3.1 With probability at least 1 - e [i(m)) over the random initialization, we have
SSan (i, t) = O(m exp(-B²//2)
for all 0 < L.1 T and i E [n], where S.m (i = (r E [m]] wr(1) x; 2 b, (1))
5

---

Under review as a conference paper at ICLR 2023
3.2 GENERALIZATION AND RESTRICTED LEAST EIGENVALUE
In this section, we present the carrsitydependent generalization of our neural networks after gradi- ent descent training. However, for technical reasons stated Section 3.3 we use symmetric initial- ization defined below. Further, we adopt the setting in (Arora et al. 2019) and use non-degenerate data distribution make sure the indth NTK is positive definite.
Definition 3.6 (Symmetric Initialization). For one-hidden layer neural network with 2m neurons, the network is initialized as the following:
1. For r E [ml] independently initialize Wrp ~ NO, I) and a, (niform((-111)
2. For r E {mm+ 1 2m), let w, = wr-m and a, = mm- 1,..., Definition 3.7 ((Aa; 6,
distribution, (Arora et al. 2019 A distribution over Rd x R is (Aa. 6, nen-deeeeeeee if for n i.id. samples {12,, Y: from D, with probability 1 we have Amin (H* 2 X >
Theorem 3.8. Fix a failure probability å E (0, and an accuracy parameter (0, Suppose the training data S {12, 1)) are i..dd samples from a (X, 5, noj--onn-geeeeerte distribution 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
2 át (A(B)=6n exp(- B²)) Consider any loss loss function E ; R. R - [0, 1] that is 1 1-Lipschitz in
its first argument. Then with probability least 28 Q(m)) over the randomness in symmetric initialization of W (0) Im xd and a E Th and the training samples, the two layer neural network J(W (1), b(t), a) trained by gradient descent for 5 nxTT log log((166) iterations has empirical
Rademacher complexity (see its formal definition Definition
C. / in Appendix) bounded as
Rs(F) S 2 (H)))(B)) Sexp( (Bxp(-B//2)
eep(( (0o(-B2/4)
1/2
n
and the population loss LD(f) (lay) ([(ff()(((()))))))))))))))))>))) y) can be upper bounded
y (THxo(()) by 32 exp( B2/2) +0
n2/2 (1112)
1
(O)) &
n
To show good generalization, we need larger width: the second term in the Rademacher complexity bound diminishing with m and make this term O(1/ VT), the width needs to have (n/X(B)) dependence opposed to (n/((B)) xf 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 that the smallest eigenvalue of H also has an exp( B² dependence. Thus, the worst case, the exp(- B2 B²/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 Then, if we let m Z (2(2(0)-6p) population loss are both bounded by
( 6n)), the empirical Rademacher complexity and
V (H y 32
Rs(F), (l), &
1/2
n
Corollary 3.9 requires the network width m 2 (((n\((0)) which significantly improves upon the previous result in (Song & Yang 2019 Theorem G.7) m 2 2(n poly(1/2(0))) (including the dependence on the rescaling factor R) which is a much wider network.
Generalization Bound via Least Figenvalue. Note that in Theorem 3.8 the worst case of the first term in the generalization bound in Equation (2) is given by O(VI/(X(B) least cigenvalue A(B) of the NTK matrix can significantly affect the generalization bound. Previous works (Oymak& & Soltanolkotabi] 2020 Song et al., (021aa) established lower bounds on X(B) with an explicit n/ dependence on under the data separation assumption (see Theorem 3.11). which
Hence, the

---

Under review as a conference paper at ICLR 2023
clearly makes vacuous generalization bound of Ö(vū), This thus motivates us provide 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. However, it turns out that there are major difficulties in proving a better lower bound in the general case and thus, we are only able to present better lower bound when restrict the domain some (data-dependent) regions.
Definition 3.10 (Data-dependent Region). Lep P.j P PwwNN(. ww 2 B, w w'x, x 2 B) j. Define the (data-dependent) region R {a E R Eiz, A:ajPij 2 min Pirr' Σizz (1
Notice that R is non-empty for any input deta-set since R7 R where R. denotes the set of vectors with non-negnnne non-negative entries, and R = R" if Pij = Pej for all i + j j
Theorem 3.11 (Restricted Least Eigenvalue). Ler X = (Zi,..., ) be points in R' with |0sll2 1 for all i E [n] and w (O, La). Suppose that there exists å [0, 2 such that
min (1 25l12 : ||= + x2l12) 2 6. (SJ[n]
Let B 2 O. Consider the minimal eigenvalue of H over the data-dependent region R defined above, i.e., let X | aER a' H a. Then, X 2 max(0, X)) where
8 6v/1-22/1 1-82/2
X 2 max
1
B 2m
e 12
e 122
π arclan
2
B
B3
2tT
2x
To demonstrate the usefulness of our result, if we take the bias initialization B = 0 in Equation 3 this bound yields 1/(2T) (rrctan((& (02/4)44((1) 02/2)) x 6/(2T), when 8 is close to whereas (Song et al. 2021a) yields a bound of 6/n². On the other hand, if the data has maximal separation, i.e., 8 = 22, we get a max
B (
B² lower bound, whereas (Sng V
V2
et al. 2021a) yields bound of exp(ex B²/ 22/22 orem 3.1 if (()) - E R. then the error can be reduced at a much faster rate than the (pessimistic) rate with 1/n² dependence in the previous studies as long as the error vector lies in the region.
Connecting to our convergence result in The-
Remark 3.12. The lower bound on the restricted smallest eigenvalue À in Theorem 3.11 indepen- dent on n, which makes that the generalization bound in Theorem 3.8 vanishes as fast as O(1/ /n). Such lower bound is much sharper than the previous results with 1/n2 explicit dependence which yields vacuous generalization. This improvement relies on a fact that the label vector should lie in the region R, which can be justified by simple label-shifting strategy as follows. Since Ry 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; yi + C 0.
Careful readers may notice that in the proof of Theorem 3.11 in Appendix B the restricted least
eigenvalue on R" is always positive even if the data separation is zero. However, we would like to point out that the generalization bound in Theorem [38 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
3.3 KEY IDEAS IN THE PROOF OF THEOREM
Since each neuron weight and bias move little from their initialization, a natural approach bound the generalization via localized Rademacher complexity. After that, we can apply appropriate con- centration bounds derive generalization. The main effort of our proof is devoted 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(yn)) since the network outputs non-zero values at the initialization. Arora et al. (019) and [Song & Yang (2019) resolved this issue by initializing the neural network weights instead by (O, k²7) to force the neu- ral network output something close to zero at the initialization. The magnitude of i 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 A' x²I) and the biases by xB. However, the drawback of such approach is that the effect of is to all the previously established results
7

---

Under review as a conference paper at ICLR 2023
for convergence need to be carefully tracked derived. In particular, in order to guarantee con- vergence. the neural network's 's width needs to have a polynomial dependence on I/N where 1/K has polynomial dependence
and 1/A, which means their network width needs to be larger to compensate for the initialization scaling. We resolve this issue by symmetric initialization Def- inition 3.6 which yields effect (up constant factors) previously established convergence results, see (Muntcanu et al., (022). Symmetric initialization allows us to organically combine the results derived for convergence be reused for generalization, which leads to a more succinct anal- ysis. Further, we replace the fi-ly 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 -parsity-inducing initialization, we present our sparsity-dependen 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 8 12(m) over the random initialization, we have for all t 2 0.
([)) [W, [W,) S V 1 /exp(- B2/ (2/2) l0g(1n00)) 3/0
m
+0 ny (eex((-B212)
exp(-B2/A)) log(n2/6)
+ R Rexp(-B² (2)
A
m
where R = Rww + Rs, denote the maximum magnitude of neuron weight and bias change.
By Lemma A.9 and Lemma A.11 in the Appendix, we have = 00= ((77)) ). Plugging in and setting
B = O, we get [[W, - [W, bW,bj00 (r) S (H y + O Xm1 +
X3/2m XVm +
3/3/2
n² ). On the other hand, taking x 1, (Song& & Yang 2019 Lemma G.6) yields a bound of FVm
[[](t) ( S VVT(H>))-yy Ö n" poly(1 Notice that the Ö x)
term has no dependence on 1/m and is removed by symmetrie initialization in our analysis and we improve the upper bound's dependence on by a factor of n².
m
We defer the full proof of Theorem 3.8 and Lemma 3.13 Appendix C
3.4 KRY IDEAS IN THE PROOF OF THEOREM
In this section, analyze the smallest eigenvalue X Amin (H00) of the limiting NTK H with 8 data separation. We first note that = = (w,,N(,,1) [1(Xw 2 B)l(( 2 B)" and for fixed vector a, are interested in the lower bound of Ew>,V((on) I(X B)}3]. In previous works, Oymak & Soltanolkotabi 2020) showed lower bound f2(5/n²) for zero-initialized bias, and later Song et al. (2021a) generalized this result to a lower bound (e ((fe-B2/2jj/v /20/n²) for non-zero initial- ized bias. Both lower bounds have dependence of 1/n². Their approach is by using an intricate Markov's inequality argument and then proving an lower bound of Piaa" | [(xw" 2 B)] Z e [[aall.)) 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 factor of 1/n since a can have identical entries. On the other hand, the diagonal entries can give exp(-B3 bound and thus there is 1/n² gap between the two. Now, we give some evidence suggesting the 1 1/n² dependence may not be tight in some cases. Consider the following scenario: Assume n << and the data set is orthonormal. For a fixed a, we have
upper
a (i [[(XW> 2 B)I(XW 2 B
Eisegm a,a, Plw x4 2 B, TT, BJ Po ||a|| + P1 Eits aaj
Po P1 + P1 (E; a.) Po P
where Po.Pi E |0, 1] are defined such that due to the spherical symmetry of the standard Gaussian we are able to let Pa = P[w" x; 2 B). Vi E [n] and p1 = P x, 2 B, w z; 2 B), Vi.j E [n]. i + j. Notice that Pa > P1- Since this is true for all E R we get a lower bound of pa Pı with no explicit dependence on n and this holds for all n < d. When d is large and n = d/2, this bound is better than previous bound by factor of (1 /P). However, it turns out that the product
8

---

Under review as a conference paper at ICLR 2023
terms with i * j above creates major difficulties in analyzing the general case. Due such technical difficulties, we are only able to prove a better lower bound by utilizing the extra constant factor in the NTK thanks to the trainable bias, when restrict the domain to some data-dependent region. We defer the proof of Theorem 3.11 Appendix
4 EXPERIMENTS
In this section, we study how the activation sparsity patterns of multi-layer neural networks change 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) 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, made a slight modification to the MLP architecture to include an extra Batch Normalization after ReLU to normalize the activation. Our MLP implementation is based 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.
(Zhu et al. (021). We train
0.85
0.750
layer 0
layer 1
layer layer
layer
0.80
layer 0
layer
layer
layer
layer
layer
0,90
0.95
layer 0
layer
layer
layer
layer
0.700
Sparsity
0.75
0.85
0.675
0.80
0.650
0.70
0.75
0.625
0.70
0.65
0.600
20k
30k
40k
20k
20k 30k
Iterations
(a) Init Bias as O
(b) Init Bias as -0.5
(c) Init Bias as -1.0
Figure 1: Sparsity pattern on different layers across different training iterations for three different bias initialization. The x and 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 O.
Observation and Implication. As demonstrated at Figure I 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%. Mcanwhile, by increasing the initialization magnitude for bias, the sparsity level increases with only marginal accuracy dropping. This implies that theory can be extended to the multi-layer setting (with some extra care for coping with vanishing gradient) and lulti-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.
DISCUSSION
In this work, we study training one-hidden-layer overparameterized ReLU networks in the NTK regime with its biases being trainable and initialized as some constants rather than zero. We showed sparsity-dependent results on convergence, restricted least eigenvalue and generalization. direction is to generalize our analysis to multi-layer neural networks. In practice, label shifting is unnecessary for achieving good generalization. An open problem is whether it is possible to improve the dependence on the sample size of the lower bound of the infinite-width NTK's ' least eigenvalue, or even whether a lower bound purely dependent on the data separation is possible so that the generalization bound is no longer vacuous for all labels.
future

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhh Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning, arXiv preprint ar Xiv:2001.004413 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 2021 JEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 2019.
PMLR,
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Tianyi Chen, Bo Ji, Tianyu Ding, Biyi Fang, Guanyi Wang, Zhihui Zhu, Luming Liang, Yixin Shi, Sheng Yi, and Xiao Tu. Only train once: A one-shot neural network training and pruning framework. Advances in Neural Information Processing Systems, 34:19637-19651, 2021.
Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang. A generalized neural tangent kernel analysis for two-layer neural networks. Advances Neural Information Processing Systems, 33:13363-1332 2020.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing sys- tems, 31, 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675- 1685. PMLR, 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
Spencer Frei and Quanquan Gu. Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent. Advances in Neural Information Processing Systems, 34: 7937-7949, 2021.
Yeqi Gao, Lianke Qin, Zhao Song, and Yitan Wang. sublinear adversarial training algorithm. arXiv preprint Xixiv:2208. 053905 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In Proceedings of the IEEE international conference on computer vision, pp. 1389- 2017.
10

---

Under review as a conference paper at ICLR 2023
Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo. Training overparametrized neural net- works sublinear time. arXiv preprint (rXx:22208.04508, 04508, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33:20744-20754, 2020.
Ziwei Ji and Matus Telgarsky. Polylogarithiic width suffices for gradient descent to achieve ar- bitrarily small test error with shallow relu networks. International Conference on Learning Representations, 2019.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. att labs, 2010.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr Snip: Single-shot network pruning based
on connection sensitivity. In International Conference on Learning Representations, 2018.
Wenbo Li and Q-M Shao. Gaussian processes: inequalities, small ball probabilities and applica- tions. Handbook of Statistics, 19:533-597, 2001.
Fangshuo Liao and Anastasios Kyrillidis. On the convergence of shallow neural network training with randomly masked neurons. Transactions on Machine Learning Research, 2022. URL
net
Chaoyue Liu, Libin Zhu, and Misha Belkin. On the linearity of large non-linear models: when and why the tangent kernel is constant. Advances Neural Information Processing Systems, 33: 15954-15964, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
Shiwei Liu,, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34:9908 9922, 2021a.
Shiwei Liu. Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. In International Conference on Learning Repre- sentations, 2021b.
Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neu- rons commodity hardware. Neural Computing and Applications, 33(7):2589-2266) 2021c
Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do we actually need dense over- preeraaramttiiizttoon? in-time vee-parameteriizatoon in sparse training. In International Conference on Machine Learning, pp. 6989-7000. PMLR, 2021d.
Tianlin Liu and Friedemann Zenke. Finding trainable sparse networks through neural tangent trans- fer. In International Conference on Machine Learning, pp. 6336-6347, PMLR, 2020.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-fres bounds and kernel limit. In Conference on Learning Theory, pp- PMLR, 2019.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature communications, 911):1-12, 2018

---

Under review as a conference paper at ICLR 2023
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning, pp- 4646-4655. PMLR, 2019.
Alexander Munteanu, Simon Omlor, Zhao Song, and David Woodruff. Bounding the width of neural networks via coupled initialization a worst case analysis. In International Conference on Machine Learning, pp.
PMLR, 2022.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameteriration: Global conver- gence guarantees for training shallow neural networks. IEEE Journal Selected Areas in Information Theory, 1(1):84-005, 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Zhenmei Shi, Junyi Wei, and Yingyu Liang. theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Conference on Learning Representations, 2021.
Zhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound. ar preprint arXir:1906.03593, 2019.
Zhao Song, Shuo Yang, and Ruizhe Zhang. Does preprocessing help training over weerpparametriiee neural networks? Advances in Neural Information Processing Systems, 34:22890-22904, 2021a.
Zhao Song, Lichen Zhang, and Ruizhe Zhang. Training multi-layer over over- ver-parametrized neural net- work in subquadratic time. arXiv preprint arXiv:2112.07622 2021b.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Pro- cessing Systems, 33:6377-6333 -689, 2020.
Matus Telgarsky. Feature selection with gradient descent two-layer networks in low-rotation regimes. Xiv preprint arXiv:2208.02789, 2022.
Joel A Tropp et al. An introduction to matrix concentration incqualities. Foundations and Trends@ in Machine Learning. 8(1-2):1-230, 2015.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference Learning Representations, 2019.
Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu. A geo- metric analysis of neural collapse with unconstrained features. Advances in Neural Information Processing Systems, 34:29820-298341 2021.
Difan Zou and Quanquan Gu. An improved analysis of training over over-parameterized deep neural networks. Advances in neural information processing systems, 32, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine learning, 109(3):467-492, 2020.
12

---

2n m Under review as a conference paper at ICLR 2023
A CONVERGENCE
Notation simplification. Since the smallest eigenvalue of the limiting NTK appeared in this proof all has dependence the bias initialization parameter B, for the of notation of our proof, suppress its dependence on and use À to denote == A(B) = Amin o (B)).
A.1 DIFFERENCE BETWEEN LIMIT NTK AND SAMPLED NTK
Lemma A.1. For given bias vector b R with b, 2 O, Vr E [m], the limit NTK H and the sampled NTK H are given as
H Em. [(( + 1) br, w Iz by)]
Hij 1
(1rt Ty) + T), 2 by, w. 2j 2 by).
Let's define = Amio (1 and assume then
O. If the network width m = 12(2 log(n/0)),
Amin Amin(H) 2 > 2 6.
Proof. Let H, L [(w)))) (T.)) X(w)). where Xwrr [R(++1)xn is defined
m
X(w,) [I(w, x1 2 b) (21, 1),... I(w, In 2 b) (Z 1)],
where (xr; 1) denotes appending the vector x; by 1. Hence H, ž 0. Since for each entry Hig we have
(H,)g = ((,,, .r) + 1)T x4 2 bys w. xz 2 b,) v 1 (10,2)))1) 2
(
and naively, we can upper bound | by:
H 2 - Hrll I
n m²
Then H= = Σm H, and [ H00 Hence, by the Matrix Chernoff Bound in Lemma D.2 and choosing m Ω( -'n log(n/5)), we can show that
P
Amin H) < _ \
< exp
1 A/(4n/m)
16
Amn
= n - exp
64n
< 8.
Lemma A.2. Assume m ((1) and exp (xp(Ba/2) O(ym) where we recall that B is the
initialization value of the biases. With probability at least 1 8, we have [H 11 S 4n exp(-B² /B2 log(n=/8)
Proof. First, have Ei( (((((,, mT) (0I,, S lexp(-B²/2)) Then, by Bernstein's inequality in Lemma D.I. with probability at least - 8/n².
log(n2/8)
2 2 log(n 4cxp(-B²/ (osp(-B//4)//// 1og(n2/8) /5)
(0) H < (exp(-B2/44)
m
m
By a union bound, the above holds for all i,j E [n] with probability at least 1 - 8, which implies
[(()) - 00 < exeex(-BB log(n2/8)
13

---

Under review as a conference paper at ICLR 2023
A.2 BOUNDING THE NUMBER OF FLIPPED NEURONS
Definition A.3 (No-flipping set). For each E [n], let S; C [mm]] denote the set of neurons that are
never slipped during the entire training process,
S {r E [m]: VI E [T] (ogu((w((1:))) - bt) sigu((w, b,)()) Thus, the flipping set is for [n].
Lemma A.4 (Bound on flipping probability). Let B 2 0 and Rw, Rs S m Let
W = (WI...., (mm) be vectors generated i.i.d. from ((00, I) and b = (bi..... bm) (B...., ........ B),
and weights W (wi,... Wm) and biases
(bı,..., bm)) that satisfy for any r E [m].
||ū,- - wrll2 S Rw and 1b, brl S Rs. Define the event
Air = (3w,, b, ||ū, wrll2 l112- S Rus 1b, b,1 S Ro, [[x, ür 2 by) + 1(x7 w, 2 be)).
Then,
P P[A S cR + R6)
for some constant
Proof. Notice that the event As, happens if and only if |ui 24 by < Rew Rs- First, if B 1, then by Lemma D.3] we have
IP [A (Rw Rb) exp(p R... Rb)3 /2) I ei RRw Rx) (expp-FF1 B² B²/2)
2
for some constant C1. I S B < 1, then the above analysis doesn't hold since it is possible that most P P[A.,r] S 2( + Rτ) vअअ exp( 02 /2)
B Ry Rs, I O. In this case, the probability
2 R.) However, since S B < 1 in this case, we have exp(-12 I exp( B2 /2) s
2
exp(-02/2) /2). Therefore, P[Ar,r] 02 (Rw + Ro) exp(-B²/2) for 02 2exp(1/2) V2x
Take
max(cı, )2) finishes the proof.
Corollary A.5. Let B 0 and Ru RS I min(1//B11. Assume that [[w, - w. and (t) (0) S for all E [T]. For E [n), the flipping set S, satisfies that
(l, (0)l22 I R
P(r S. S of Rew + Ro) exp(-B? -B2/22)
for some constant e, which implies
Plvi E [n]
[S.| < 2mo Rew + Ro) exp(exp(1))) B22 2 exp ( Re Rxp(xp((
Proof.
The proof is by observing that PPrr E 3.) S P[Arr] Then, by Bernstein's inequality,
(-mec Rop + Rτ) exp( -ap(-BBo B2/2) + 1/3
2/2
P[SS|| > 1/ S exp
Sexp
Take t = 2mc(R + R₂) exp( B²/ and a union bound over [n]. we have
PlVi E [n]]
[3.] < 2mc(Rn, + Ro) exp(-B2 2 1 - n exp (-3 mc mo(Buu Raw + Ro) exp(-B²2))
A.3 BOUNDING NTK PERTURBING WEIGHTS AND BIASES
Lemma A.6. Assume X > O. Let B > and Ro, Ru I min Let W = (w....., wm) be
vectors generated i..dd. from (0, I) and i = (b1....,
.......,,, bmm) = (B.... B). For any set of weights
W (W....,, wm) Wm) and biases b = (bI,..., .,)) that satisfy for any r E [m], [ we 2 S R.
and b6, - brl < Ro. we define the matrix H(W, b) E Rnnx by
H,y b)
m Σ (a,,, 23) + 1)[(w, x; 2 by. W. xj 2 b,).
It satisfies that for some small positive constant C,
14

---

Under review as a conference paper at ICLR 2023
1. With probability at least 1 n² exp (-3 5/4 ccm(Ru Rw + Rb) exp(-B2/22 have
H H(W, b) H(W, 6)
- n Rm + Rb) exp(-B2/22)
<(W, b) - Z(W, 6))
- Vnn n Sc{ Rw + Rb) exp(-
2. With probability at least 1 n² exp (- cm Rw Rb) exp(pp (B)).
min (HW,))) > 0.75A -0(88ccf, + R&) exp((BB²
Proof. We have
|| 2(WWb)- 2(,, 11 200i Σ
[[ - x; 2 b,) I x; 2 b,))²
Σ
iE m)]
rm(m)
Σ
tr
m
EE ml
rE(m]
and
H(W.b)- -(W b)]
Σ (Hy (.,(W, B))
VE(M), JE[N]
2
< m
Σ
Σ
[[, x: 2 br, w. 2g 2 b,) - I( xs 2 br, 10, xj 2 b,)1
iE[n), jE(n]
rE(m]
2
Σ
re[m]
where we define
Sr.i.j = [[w, T 2 by w. xÿ 2 b,) T( vi 2 8, W x. 2 b,)1
b (I(w,. x4 2 b,) - 1(ū, x; 2 6.))).
Notice that 4,3 only if the event Ai.r happens (recall the definition of Asr in Lemma A.4 and 8r.i. = 1 only if the event Ai, or Air happens. Thus,
Σ 1.. S Σ T(Arr), rE[m]
Σ rE/m]
Spij S Σ T(Air) + I(Ag,r).
rE[m]
rE[m)
By Lemma A.4 we have
Egg, [sppa]]
Egg. 1s 182
P P[A P[A < 2c(R,, (oxp(-BB/2)
di
Wr
Define 8i,j
m I(Air) I((Arr)) By Bernstein's inequality in Lemma D.I
P [80.5 2 m. m.2e((P Ry + Rτ) ex)(xx(BB222 + md]
m221/2
$ exp
m 2c(R,, + Rs) exp(- hap(-B2/22 + mt/3)
Wt 120 0.
Let t = Bo + Rb) exp(-B32/2 /2). We get
2 cm (-2 (exp(BB2/2)
P(sts 2 m 4c Ro) exp( BB222] exp
15

---

Under review as a conference paper at ICLR 2023
Thus, obtain with probability least 1 - n² exp (- (-3om(Ra Rw + Rb) +R))xpp(-1 exp(-B² /2)). H(W, b) H(W.b)
S n 8c( (Ro + Ro) exp(-BB2/1
Z(W,), b) - Z(W,b) b)
- Vn 80 Ru + Ro) exp(- -B2
For the second result, by Lemma A.1 P P(Aminl (HW 8)) 2 0.75A] 2 1 8. Hence, with probability least 1 - 122 exp (-3 fam Re + Rb) exp(- --2/22)
Amin (H()))) 2 Amin (H(W,b) b))
b) H(W.)) 5)|l
z Amin (HW 6))
(WW6)) - ((V
0.75A n Sc( + Rs) exp( cxp((-B212)
A.4 TOTAL MOVEMENT OF WEIGHTS AND BLASES
Definition A.7 (NTK at time 1), For 1. 2 0, let H1)) be an n x n matrix with (4, ()-th entry
H1₂()) Of ((((0(())) af(z;;0(1) a0(()
1
(1),,))) 1)T(w((1) aq 2 by ((), wr (1) æ. 2 (()).
a0(t)
We follow the proof strategy from (Du al., 2018 Now we derive the total movement of weights
and biases. Let f(t) = f(X; where (((t) = f(z; (()). The dynamics of each prediction is given by
10f(z;;((t) d0(t) 00(1) {0(())
n
0ff(z;(()) (f(x;;((t) 80(()
dt f((t)
(U) - ft())) Σ j=1
Σ
(ys - 1,00)
dt
80(()
j=1
which implies
d f(t) Hyt)(y((tt)) - f(t)).
(4)
dt
Lemma A.8 (Gradient Bounds). For any 0 St. we have
@T(W b())
n
[I((s) - vl12
(s)
1
(L) b(s))
l[f(s) 21l2
(by(s) (s)
1
m
Proof. We have:
OL(W(s),
Σ
()) 2, 2 b,)
(s)(s)
7
[f(;; ((s, - 3il
m
n V
[[((s) 211
where the first inequality follows from triangle inequality, and the second inequality follows from Cauchy-Schwarz inequality.
Similarly, also have:
dL (L.
- mm
n =
Σ
(()) (w, x 2 br)
(s)
2
16

---

Under review as a conference paper at ICLR 2023
(m W (s)) mxl
71
[[((s) - 2112
A.4.1
GRADIENT DESCENT
Lemma A.,. Assume À > O. Assume l1 f(k)]1 - (1-11/4)** 11y - f(0) 12 holds for all kl S k. Then for every r E [m]]
||,, + 1) - (s)(1)122 - 8y7 11 S(0)l22 = Dwn
Vmd
8y 11 f(0)]22 : Do.
5
VmA
Proof.
OL(W(K'))
1w (k: +1) - wo,(0)ll S " Σ
Owr(k')
k'
2
71
11 s(k)ll2
m
K==0
17
(1 7//4)4//2 lly f(00)
m
n
m\/8)* 11 - f(0)122
(1 n///s" M1 f(0))22
8 VmÀ
Il
s(0)l2
where the first inequality is by Triangle inequality, the second inequality is by Lemma A.8 the third inequality is by our assumption and the fourth inequality is by (1 x>)//² 1/2 < 1 x/2 for x 2
The proof for b is similar.
A.4.2 GRADIENT FLOW
Lemma A.10. Suppose for 0 S 3 S t, Amin (s)
2 A > 0.
Then we have |yy f(t)l <
2
exp(-Aot) 1 f0)11 and for any E [m], [[,, (t) w. (0)ll2 s
S and 16, (t)
vmdo
b,((0] S f(011
vmmoo
Proof. By the dynamics of prediction in Equation we have
d lly f())l2 = -2(y f(t)) T (1))(v- - f(t))
dt
S - 11y - -
which implies
- f(-)( < exp(->ot) 11u 1lt-(()))1
17

---

Under review as a conference paper at ICLR 2023
Now bound the gradient norm of the weights
ds
Wr (8)
=
Σ
M - [((b))
vm
Vm (10r) 2 b(o))
1
1
1=1
v mm
(.fi(s)]
1リ- f(5)122 -
expl->os) 11y f(0)ll2
vm
Integrating the gradient, the change of weight can be bounded as
(t),(t) w. (0)1l2 - ("'
d
vn 11 f(0)l2 ds
(s(
do
Vmn
2
For bias, have
d
(s)
Σ (t -i((s)
a, (,)((w xs 2 b(s))
ds
=
Vm
2
a
vn lly 1-)f(s))l2 S vm
vn /m
M f((s)1
cxp(- (ool->os) 11v f(0)ll2-
m
Now, the change of bias can be bounded
/'1) d
ds w,) ds v 11 f(0)1l2 v vmd
(t) - (0)l2 1
A.5 GRADIENT DESCENT CONVERGENCE ANALYSIS
A.5.1 UPPER BOUND OF THE INITIAL ERROR
Lemma A.11 (Initial error upper bound). Let B > be the initialization value of the biases and all the weights be initialized from standard Gaussian. Let ō (0,1) be the failure probability. Then, with probability al least 6, we have
[lf( 1 O(n(exp(-B")) B²/2) + 1/m) log (mng (mm/8)).
(I((0) - v11 O (n n (exp(-B2/2) 1/m) log" (2mm/6))
Proof. Since we are only analyzing the initialization stage, for notation ease, we omit the depen- dence on time without any confusion. We compute
l1v 1112
Σ (vi f(xx)) 1=1
m a,olw x2 - B3)
Σ
m
i=1
m Laoow x B) )
Σ
Vi
y1
(w. x3 B)+ m
Σ
m
Since w.J x3 ~ (N 1) for all r E [m]] and E [n], by Gaussian tail bound and a union bound over r, i, we have
Pl E [n), j [m]: : W x, S 2ogg(22m//) 2 55/2.
Let E, denote this event. Conditioning on the event E,, let
1 Zi, Vm ar min { (o( xz B), / logg2mm//0)
18

---

Under review as a conference paper at ICLR 2023
Notice that 2,, # 0 with probability most exp(-B²/2)) Thus,
- - 2 log(2mn/0).
Ea. w [22,1] - exp(-B3
By randomness in Or, we know B[2úr] = 0. Now apply Bernstein's inequality in Lemma D.1 have for all
we
>
8/2 -minn 4eep(- (B2)))BB/2))))) (0gmmm/8)) 2 log 2mm/6))
/mt/2
PP
Zi,r >
S exp
Thus, by union bound, with probability at least - 88/2, for all i E [m].
2 log(2mm//5
Zir S
- -2
1og(2n/00
(gexp(-B3/4)+2400
log 1/ (2mm/6).
Let Eg denote this event. Thus, conditioning on the events EJ, Eg. with probability --6. 8,
2
11((0)12
O(n(exp(-B2/ 1 1/m) log" (mn//8)
Firr
and
- (00)((0]1
2
m
21
m
Σ
Vi 2
31
Σ
Zi,r
i=1
r=1
Vi
2
+
Σ
lyel (2exp(-B²) B3 -B//4) 2 2/m) log 3/2 (2mm//8))
(2cxp(-B3)) + 2 2/m) log (2mm///)))))
i=1
0 (n (exp(-B2/0) 1/m) log (2mm/6))
where assume y; (() for all E [n].
A.5.2 ERROR DECOMPOSITION
We follow the proof outline in (Song & Yang 2019 Song al. 2021a and generalize it to networks with trainable Let us define matrix H similar to H except only considering flipped
neurons by
(k) = Σ
((11, + (k) an 2 (k), (k) x, 2 (k))
rE3,
and vector U1, 02 by
Σ
(a(Ws, + 1), - -,,k o(w,, b, (k))).
U1 = Vm
reS,
( (a(((w, 1), by(k + 1)) a (k), b, (k))).
02 =
rES,
Now we give out our error update.
Claim A.12.
lll - f(k + 1)11 11v -(0)) B, B, By + Ba,
19

---

Under review as a conference paper at ICLR 2023
where
B1 27(y f())) (V f(k)).
B3 2 f(K)) 11 f(K)),
B3 = 2(U - -(())) 02.
B4 = 15(k: + 1) s(k)
Proof.
First we can write
Σ or
(((
(x)(k)
OL
.zi) (2,(K) -10b,)
Ob, )) ((wrr()), b²((
OL
11
17 Ow.,"
V m
rES:
ØL
+ 11 ØL ab,
I((20((k), b,(k) 2 0)
ar
11 ow,
24
rES;
Σ (3
(((5))) + (k) 2 (x() (4), - b,((k) 2 0)
dr
m
m
rES:
(u (H())) 117(1))
which means
U1 = (())()) (1)
Now we compute
ll - f(k + 1)112 = lly f(k) - ([(++)-f(b)1]
= 11y fk)] (fy-)(k)) ((()))((((()))))))((((((()())( (f(k+ 1) f(k)) + 1i(k + 1) f(k)
Since ʃ(k +) [k) vı U2, we can write the cross product term as
(u ((()))((((+))))))))) (1( s(-)) (y [(k)) (v) + +2)
(y ((k)) Tn (y- -(()) 02
+7v - S(A)) H())(y f(k))
nTV f(k)) H (k) f(k)) + (v ((:))TT2 02-
A.5.3 BOUNDING THE DECREASE OF THE ERROR
Lemma A.13. Assume O. Assume we choose Ra, Ra, B where Rw, Rg < min(1/B,1) such
that 8cn Scn(Ry + Ro) exp(- (B22))B/)22 S X/8. Denote dy = 8 h exp( 5c R + Rb) exp(-B' (B/))) Then,
P[B < -155 lly (f f(:)1
-80-
Proof. By Lemma A.6 and our assumption,
Amin ( H (W)) > 0.75A n Sc Rop + Ro) exx(-B2/22 2 52/8
with probability at least 5g. Thus,
f())) H(N)(U (())))-))))>>)))))00000))))))))) 2 11 52/88
20

---

Under review as a conference paper at ICLR 2023
A.5.4 BOUNDING THE EFFECT OF FLIPPED NEURONS
Here bound the term B2, B3. First, we introduce a fact. Fact A.14.
4n S
||
Σ 1..1P
m 1=1
Proof.
2
| (4)]
Σ
1
( Ty (k) xs 2 (k),, wrr w.) 2 br (k))
m
iJE
r
L
4n
n
s Σ
2 21.11
1
1.1.2
m² 2
i.jE(n]
i=1
Lemma A.15. Denote 8n = =neep((=-> 3mm Rew + Rb) exp( -B2222)). Then,
P[B₂ S Rr + exp( B2 /2) 11y [(k)] 2 5g.
Proof. First, have
B2 S 27 11y f(()) 1 (1))12
Then, by Fact A.14
H (1) = H 1 [1)] S
4n
|.,12.
m
i=1
By Corollary A.5 we have
Plvi E [m] [S.| s 2mc( Rew + Ro) expp(=B2/22 2 50-
Thus, with probability at least 6o.
L (k))l2 S 4nc(Rw + Ro) exp(x-3333
Lemma A.16. Denote 8n
+ Ra) exp(ep3p) 12)). Then,
P
4cnn Rw + RR) exppp-B3 (B2222 |yy [ 50-
Proof. By Cauchy-Schwarz inequality, we have B3 < 2 ||y [(:))l2 1|02|12- We have
|02
1
<
1
Σ
aL Ow,
|
+
ØL
i=1
rEB.
n
1/2
(K
Ôl Owr,"
2 ab, 1)
aT.
max iE|n
+
|5,12
m
1
2 m [I] 2|12 2mc Run + Rs) 1xpp-B32/1 2
< n
m
= 16c 17 n²
1y f(k) (Ru + Rb) 2 exp(-133)
where the last incquality is by Lemma A.8 and Corollary A.5 which holds with probability at least
1 5g-
21

---

Under review as a conference paper at ICLR 2023
A.5.5 BOUNDING THE NETWORK UPDATE
Lemma A.17.
B4 S 41fn²² Ily [1
new result:
B4 S C2n 118 [(1)]12 exp(- -B²).
for some constant Cz.
Proof.
ØL Ow. 2i >l
OL Ab,
I[skk + -
- Σ 1=1
S 44y |1 f(k))
New Proof. Recall that the definition that Sn (t, t) = fr E [m] : wo (t)T,; x; 2 b,(t)), ie., the set of neurons that activates for input z; at the t-th step of gradient descent.
2
[lf(k + 1) f(A)112
n
Σ
ØL Oww B4
ØL
Vm
Öb,
E. (3.k (t.k)
n/² (IS (1, h + 1)1 Sea 1)1)
(K
aL Ow,
aL ab
$ n
max
+
m
sEIn|
1²2
2
< (Camexp(-B"
11 - [(K)]l2)
m
S n ly - fk:)l -22).
where the third inequality is by Lemma A.19 for some C2.
A.5.6 PUTTING IT ALL TOGETHER
Theorem A.18 (Convergence). Assume
0. Let 1 I a/(64n2) n
Ae
B
3Cfn²
[0, /0.5log m] and
2 12 (2(2-4 (1+ (exp(-B") -B 1/m) log (2mn/8))) exp(-B²)
Assume X = An exp( B22 22) for some constant λa- Then,
P Vt: |Iv f(0112 = (1 nA/4)* by 1(0)) 2 21- -
Proof. From Lemma 1.13 Lemma A.15 Lemma A. and Lemma A.17 we know with probability
least 1 2n exp( foml RR,, + Rb) exp 1 /2)) 8, we have
Ill - flk + 1>113 < lly (1) (1 - 5m/288 + 12mno Rw + Rt) -B2/BB// + nn)
lly - f(k + 1) ly - f()))l (1- + RR + Ro) eexp(=B)) + CZ2 nn 1 - exxp1 (exp(=B"))
By Lemma A.9 we need
D. 8yn Fly f(0))22
< Ras
Vml
D3 8/7 1lv f(0)1l2
< Ro.
VmA
22

---

Under review as a conference paper at ICLR 2023
By Lemma
A.11 have
()) ull2 = 0 (n (exp(-B2/22 + log (2mn/
Let R min(Rw, Ro): D max max Pwo Db). Combine the results have
R> 1-000110 1
ny (exp(-B2/2)) + 1/m log" (2mn/6)).
Lemma A.13 requires
Be + Rb) exp( exp()B2/22 s 2/8
Aexp(BB212)
R 128cn
which implies a lower bound on m
m 2 S2 (A *n (1+
(exp(-B²/2) + 1/m) log (2mn/8) exp(-B²))
Lemma A.1
further requires a lower bound of m 2-(A-''nnn 'n log(n/0) which can be ignored.
Lemma
A.6
further requires R min(1/B,1) which implies
128cn
A expl Aexp B3)2)¹
n
n (1+ (exp(-B²/2) + 1/m) log (2mn//)) (xp(-BB)))
From Theorem F.1 in (Song al. 2021a we know that À Ao exp(-B22 for some An with no dependence on and exp 13 (2) - 1. Thus, by our constraint on m and B, this is always satisfied.
Finally, to require
12 + Rb) ex)(-222) 442 S n//4.
12mnc(RRs + Ro)
+ C2n exp( - B²) S 1//4
we need S 2/(6422) n 5
\e DCjn²
By our choice of m, B, we have
2
2n exp( eem(Re Ruw Ro) exp(-B22/2) -2(m))
A.6 BOUNDING THE NUMBER OF ACTIVATED NEURONS PER ITERATION
First we define the set of activated neurons at iteration for training point 2; to be
Sin t) = fr E [m] (t) T x4 2 (t))-
Lemma A.19 (Number of Activated Neurons Initialization). Assume the choice of m Theo- rem 4.18 With probubility at least - e (()))) over the random initialization, we have
[San f)l Om (tmm-exp(-F)) exp(-B2 (Bp(-B)22)).
for all 0 < StsT T and E [n], And As by-product,
[z(00] < 8nexp(-13²/))
Proof. First we bound the number of activated neuron at the initialization. We have Plu x, 2 B² /2). By Bernstein's 's inequality,
B] I exp(-B2
Pl|S.a (1, 0)1 2 exp(pBB2222 exp (- ("mexp(-B") + t/3
12
23

---

Under review as a conference paper at ICLR 2023
Take f exx(-BB²/2) we have
PllS (i, 0)l 2m exexx(-BB B- B2/2) 1 exp (mmex(BBB/22)
By union bound over [n|, we have
PIvi [n] (i, 2m expl (xpe(=B2/22) 2 nexp (-mexp(-B32/2) /2)/4)
Notice that
|Z
I, S 8n expeexeBBBpp
Lemma A.20 (Number of Activated Neurons per Iteration). Assume the parameter settings in The-
orem A. 18 With prohability at least - e eQ(n over the random initialization, we have
Sm (1, t) O(m exp(- /2))
for all 0 < 1 T and i [n].
Proof. By Corollary A.5 and Theorem A.18 we have
Plvi E [n]
[S s 4mcexp(-B²/2)) 21 e
Recall S; is the set of flipped neurons during the entire training process. Notice that (i, f) -
[San (t, 0)| + [5.]. Thus, by Lemma A.19
Plvi E [n]] |Son 6) = 0mmexp(BB3/)) e-R())
B BOUNDING THE RESTRICTED SMALLEST EIGENVALUE WITH DATA SEPARATION
Theorem B.1. Let = IT.) be points in Rd with ||0i|12 1 for all i E [n] and NO Ia). Suppose that there exists E [0, 2 such that
min (||=; xzllı : ||, + x, 2 d. (/jE(m)
Let B 2 O. Recall the limit NTK matrix H defined
H (o [((r,, 1)T(w 34 B,w w zzj B)
Define po = F[w I1 2 B] and P.j P(w x; 2 B, w TT, 2 B) for # j. Define the (data-
dependent) region R {a E E Eits a,a,Pij > min P..j Σits a,az} and let
min aER a 2 a. Then, X 2 max(0, X)) where
X Pa ifj
min pij
6VI-82/4 1-84/2
1
B
e /2
-B-211(262/))
aretan
max
2
2m
B3
/ 2m
2T
Proof. Define A m (2,, 2zy) ). Then by our assumption.
((nn,ey((1z; 2, 22112
|| + xz 12)
1 A max (z),,
> 82/2
2
A < 1 8//2.
24

---

Under review as a conference paper at ICLR 2023
Further, we define
(ww) == [xil( To 21 2 B), xz]( T 22 2
In 2 B)] E R
Notice that H = Em--N(0.n) [Z(w) T ((w) + +[x 2 ( 2 B) We need to lower bound
min |
a==0== min a T Ewwor(o [z))) Z(m)] 1el|2=1,aER
+ ta Bosnn [[(X B)I(XW B
min a E EwwNN [[(x 2 B) 2 B) a.
||l| ,EER
Now, for fixed a,
(O0 [T(x 2 B)T(X 2 B]]
a Σ a Plo x, B] + Σ
aja Plw x4 B, wT x. 2 B
ifj
= P |1a|2 + Σ
aguyPij
in
where the last equality is by Pfw x1 BJ symmetry of standard Gaussian. Notice that maxist Pij S po. Since E R.
P/w7 In 2 B] Po which is due to spherical
Ew-N [(a 1(X 2 B))²} 2 (po mm) ||a| + (min p(g) ||a12 + (min pij)
Σ
a.ag
ifj
#F
15
igj
2
(po - minp:;) | + (m)n
Σ ai
(f)
Thus,
A
min
Ew,)) [(a I(XW 2 B
|a|
L
2
min
(po - min p ||a| 1aa)) ||l LR (f)
min (min
[||]
Po
min Pij. {g
Now we need to upper bound
min Ptj max Pij- L4
(f)
We divide into two cases: B = and > 0. Consider two fixed examples 2 22. Then, let (I x / [[(I x 2 |az|| and = (x1,
Case 1: B First, let us define the region Ag as
An {
V1- ~
(01.92) IR
91 > 0, 91
92
Then,
Pww æ 2 0, w T x2 2 0] = Plw xn 2 0, w T (c(c + v1 - 2v) 2 0]
Pigı 2 0, cgi + v 22 92 2 0
P[Ao]
VI-
arctan
2T
'eere we force to be positive. Since we are dealing with standard Gaussian, the probability is exactly the same if < by symmetry and therefore, force > 0.
25

---

Under review as a conference paper at ICLR 2023
π arctan V1-A2
2T
where we define 91 := w 21 and = w and the second equality is by the fact that since and e are orthonormal, 91 and 92 are two independent standard Gaussian random variables; the last inequality is by arctan is a monotonically increasing function and X- is a decreasing function in |c| and |c| A. Thus,
V--A" π arctan
A
min Pij
S max
(F)
17j
2T
Case 2: B >> O. First, let us define the region
B
v1
-1-
(21.92) E R 91 B
92
c
c
Then, following the same steps as in case 1, we have P(w T 21 2 B, w T 02 2 B = Plg 2 B, ey + v 1 - - 2 B] = P[A].
Let B1 = B and B2 = B
Further, notice that A = Ao + (B1, B2). Then,
P[A|- = M.
g + 92
exp
dgi dg2
(01 2T
2
(01 + B₂)² + (g2 + B₂)²
exp
dg1 dg2
2T
2
= -B3++BB
exp 1-Bigi B292) exp {
ot
+
dgi dg2-
(g1.92)EAo
2T
2
Now, Bigi + B292 Bgi + BV 1=g
2 0 always holds if and only if g1
g2 92. Define
the region A. to be
A+ = E 91 2.
1-c c
1+c
Observe that
1+c < v
c) +
# #c 1
C
Thus, Ao C A4. Therefore,
P[A] < e (B)+B3)/2 -
gi + 92
exp
dgi dgz
(01.90)E.A
2T
2
(BI++BB)/ P[Au]
V- lel
-e arctan
2
A-
Se 12 /(1+a) ग arctan
A
2π
Finally, we need lower bound po- This can be done in two ways: when B is small, we apply Gaussian anti-concentration bound and when B is large, we apply Gaussian tail bounds. Thus,
B
1
1
e- B2/2
Po P(w x1 2 B) max
V2T
B
B3
22T
Combining the lower bound of po and upper bound on max Pij we have
(I-3²
A Po min Pia 2 max 1 1
B2
e B²)(+)))
arctan
|
iデj
2
B3
2m
Applying A < 1 82 and noticing that 0 is positive semi-definite gives our final result.
26

---

Under review as a conference paper at ICLR 2023
C GENERALIZATION
C.I RADEMACHER COMPLEXITY
In this section, would like compute the Rademacher Complexity of our network. Rademacher complexity is often used to bound the deviation from empirical risk and true risk (see, c.g. (Shalev- Shwartz & Ben-David 2014).)
Definition C.1 (Empirical Rademacher Complexity). Given n samples S, the empirical Rademacher complexity of a function class F, where f R for f E F,,, is defined as
(F(F) -E n
sup SEF
(f()))
where e (EI,...,En) and e, is an i.i.d Rademacher random variable.
2014)). Suppose the loss function -(- is bounded in j0, c| and is p-Lipschitz in the first argument. Then with probability at least 8 over sample S
Theorem C.2 (Shalev-Shwart &
of size
(og(2/0)
sup LD(f) Ls(f) < 2pRs(F) + 30 feF
2n
In order to get meaningful generalization bound via Rademacher complexity. previous results, such as (Arora et al. 2019 Song Yang 2019), multiply the neural network by scaling factor x to make sure the neural network output something small at the initialization, which requires at least modifying the previous lemmas we already established. We avoid repeating our arguments by utilizing symmetric initialization to force the neural network to output exactly zero for any inputs at the initialization. E
Definition C.3 (Symmetric Initialization). For one-hidden layer neural network with 2m neurons, the network initialized as the following
1. For r E [m], initialize w, 10, and a, Uniform((11,11)
2. For E {m + .,, 2m), let w, wr-m and 0r -Qr-m-
not hard to see that all of our previously established lemmas hold including expectation and concentration. The only effect this symmetric initialization brings is worse the concentration by a constant factor of 2 which can be easily addressed. For detailed analysis, see (Munteanu et al. 2022).
In order to state our final theorem, we need to use Definition 3.7 Now we can state our theorem for generalization.
Theorem C.4. Fix failure probability 5 E (0,1) and an accuracy parameter (0, Suppose the training data {(x,,y:)] _ are i.i.d. samples from a (2, 8, nen---eeeeeee distribution
D. Assume the settings in Theorem A.18 except now we let
m 2 52 (2 (1 (exp( B2/2) + 1/m) log (2mn/5)
Consider any loss function e: R R 1] that is 1 1-Lipschitz in its first argument. Then with probability at least 28 e - ())) over the symmetric initialization of W(0) mxd and Rm and the training samples, the two layer neural network [[ (k), b(k),, a) trained by gradient descent for k > Q2 1 log a nlog(1/5)) iterations has population loss LD(f) (( ((((())) 2) upper bounded as
1 (1 -1(p)))-yy3322__1211 e2xpp((BB222 +
Lo (W)) &
72
1/2
WWhile preparing the manuscript. the authors notice that this can alternatively solved by reparam- eterized the neural network by f(; W) - f(x; Wo) and thus minimizing the following objective L "/ (fz; W) fæz; Wo) - ) The corresponding generalization is the same since Rademacher complexity is invariant to translation. However, since the symmetric initialization is widely adopted in theory literature, we go with symmetric initialization here.
>>
27

---

Under review as a conference paper at ICLR 2023
Proof. First, need to bound Ls. After training, we have [lf( ull2 S 1, and thus
((f((k)) ((ve.
(f((k)
- Yil
[[f(k) 2l12
1
By Theorem C.2
know that
Lo()(W &
2Rs(F) (n=1/3
(F) 1/2).
Then, by Theorem C.S
we get that for sufficiently large m,
(H 20)0001000 -y exp((-B3/2)
+ exp(-BB//4)
Rs(F) S
n1//2
7
(H -ex.8ex((-ppp +0
n2//2
where the last step follows from B > 0.
Therefore, we conclude that:
Lo(f(W S T (H100-1 yy 32 1aspp-B2/22
1
+
1/2
n
Theorem C.S. Fix a failure probability å (0, 1). Suppose the training data S = {(Ti, y:) are i..dd samples from (2, non-ndn-dggeeettee distribution D. Assume the settings in Theorem A.18 except now we let
m 2 1 (1+ (000--BB22++1mmm/ log (2mn/8) exp(-B²))
+
Denote the set of one-hidden--laer neural networks trained by gradient descent as F. Then with probability at least 1 - 28 e -S(()) over the randomness in the symmetric initialization and the training data, the set has empirical Rademacher complexity bounded as
1 y. 8cxp(-B2/2)
cxp(-B2/44
Rs(F) S
n//22
Note that the only extra requirement we make m is the (n/X)6 dependence instead of (n/X)² which is needed for convergence. The dependence of m on significantly better than previous work (Song & Yang 2019) where the dependence is 14,4, We take advantage of our initialization and new analysis to improve the dependence on n.
Proof. Let R., (R&) denotes the maximum distance moved any any neuron weight (bias), the same role as Dw (D;) in Lemma A.9 From Lemma A.9 and Lemma A.III and we have
max max(Pno, Ro) 0 a 1+ (exp(- /3/22) 1 1/m) log (2mn/5)
Vmd
28

---

Under review as a conference paper at ICLR 2023
The rest of the proof depends the results from Lemma C.6 and Lemma C.8
Let R
II, (b)) - ([) p. By Lemma C.6 we have
8exp( B2)22
Rs(FRo. RV
4c(Rw + Rb)² wwwppp-BBBBppp/p
n
Sexp( -B212)
+0 n22 (n²(1+ (exp(-B B2/2) + 1 1/m) ) log log (2mm/8))))))) exp(-B212)
$ RV
vm22
Lemma
C.8 gives that
log(n/0) [cxp(-BB B3/ /B/0)////1/))// 1008(1/01)/ 1/41
n (R + Rb) (a))ex((-1 exp(-B²/2)
R E (H
( +0000
(
+0
m
log(n2 (o) + X exp((=B2/10 /2)
(Rw + Ro) Rx)) exp /2)
132
m
Combining the above results and using the choice of m, R. B in Theorem A.18 gives us
(1100
/nexpp(- -B²/2)
exp(-B3 /2/2)//22)) log(n/8) 1/4
R(F) S
+0
Vn(R.. + +Rs) Aexp(B2/22 /2)
Vn
(B2//)) 1og(n2/0) + (Ra exp(-
+0
+
O
exp(-B2
X
(aai)log""("mmnnm n² n2 (exp(-B3) B-/2)/22)))) + 1/m) log" (2mn/ (xpo)))xp(--13 exp(-B2//2)
Vm
Now, we analyze the terms one by one by plugging in the bound of and Ra,, Rs, and show that they can be bounded by Ó(ex((-B² /4)/n/////// /2)). For the second term, we have
(nexp(-B3/2) eexp(BB²) log(n/0)
3/4
=0 VAexp(-Bi log 1/4 (n/0))
For the third term, we have
Vn(Bu + Rs)
vn(11 (exp(-B (B22(-BB))))) + 1/m) (2mn (amn/8)) 18) Aexp(B2/2)
Vn
0
(eex((B212)
22/411/2
exp(B2/22nbb/4eg) 1//n///xx(p-- B2/4))
exp(-B² /B244) /4) n²/2
For the fourth term, have
Vn
log(n2/6)
O
exp( -B2 -B)))
+ (Rw + Ro) exp( exp(-3B2/4)
X²
A Avlog(n/8)
(Bp(-B2/44)
+0
n2.5
11.35
For the last term, we have
n²( + (exp( 1220(BB2112 B2/2) + 1/m) log (2mn()m//)
Vmd²
A 1 (exp(- + 1/m) log (2mn/8)
Recall our discussion À in Section 3.4 that À Ao exp(-B2/11 < 1 for some Ào independent of B. Putting them together, we get the desired upper bound for R(F). and the theorem is then proved.
29

---

Under review as a conference paper at ICLR 2023
Lemma C.6. Assume the choice of Rw. Ry. in Theorem A.18 Given R O. with probability at least 1 6 -2(m)) over the random initialization of W WO)), a, the following function class
FR.. Re, R (f(W, b) I|W (00)ll..0o Rw: |b b(0) S Ro.
[[ 6] [0), 6(0))il R}
has empirical Rademacher complexity bounded as
(exp(-B2/13 4c(Ruw cxp(pppppp /2).
RR(FR... & RV
n
Proof. We need to upper bound (F n.. Define the events
Ar. = {|u, (0) I; b, (0) S R. + RoJ: i E [m], r [ma]
and a shorthand 1(w,((0) xi - 2 0) = 1 (0). Then,
a w - b,,) -
Σ
a, (0) x; br)
i=1
r=l
Eiar (o(w, X4 - b,) - I0, xi -b))
((A (a(w, xs - b,) (O) br))
I(A,))c;ar (o(w, xx b,) (,:(0)(ww, b,())) - I,, w.)( x; (b, b,
T( ((A,)) (o(w, v; bx) (0) x; b,)) (0, - (0)
(br b-(())))
I(Ar,))((Rr + RR), ==
where the second equality is due to the fact that ( x; b,) = (0) xs b,) if & A Thus, the Rademacher complexity be bounded
Rs( (RRRR... (R...R..RR) R..
0 oww x4 - -r)
E. [W- R [ RR.
sup
n
m
1
E.
sup
a
E2
m
0
(0) xs br)
2(R + Ro)
n
I(Ar.)
11
|W -W R [O) < Rb.
m
n m
1
2(Rrr + RR)
E,
sup
vec (W, 2(0)c
T T(A,,))
n
[]vec[[W.6 (W
n/m
1=1
1
2(RGp + Ro)
E,
sup
vec( b(()))
I(Ar.)
11
W,, (W(())
nym m
1 E. ((0)](
2( + Rb)
T(A,s)
n/m
r=
E. [.(])((0) + 2(H + Ro)
<
Σ
I(Ars)
m/m m
30

---

Under review as a conference paper at ICLR 2023
R
2(R + Ra) nym m
T(Ar)),
where we recall the definition of the matrix
(0) 11" (0)a 1|T
Z(0)
1
E 1gm(d+1)x
V'
I [r], -1] Mm, (0)am [1 _]_
By Lemma A.19
we have
||((0)] S / expl B2/2) and by Corollary A.5 we have
m
[m] Σ I(Ar)) 2 2m + Rb) exp(xB222) - 21-e-(m))
Thus, with probability at least e-R(n), we have
8exp(-B2// + 4c + -R)) mxxp((BB
Rs(FRR.RooRl S BV
C.2 ANALYSIS OF RADIUS
Theorem C.7. Assume the parameter settings in Theorem A.18 With probability least Di() over the initialization we have
f(k) - -- e(k),
where
/log(n//0) /10//o/((n200 + (Ri + Ro) exp) exp(-B2222
[|c(k)]l2 k(1 ( 1)/2 mm O (yp(-B2/4)
m
Proof. Before start, assume all the events needed in Theorem A.18 succeed, which happens with probability at least - ö e((())
Recall the no- fo-piiping set S, in Definition A.3 We have
1
fi(k + 1) fi(k) =
(w, (k + 1) x; - by + 1)) (ww, x; - b, (k))
au la (w (k: + 1) x; - bk 1)) (k) b, b,()))
m
rES.
a, (o (Ic + 1)) x4 6k + 1)) (k) x, - (b)))
Vm
rES,
c((k)
(5)
Now, to upper bound the second term (k())
[c(())] =
Σ
ar (wr (k: + 1) x; - by(k + 1)) - (wrr()) - b,(k))]
r
Iw. (A T)TTa x; b, + 1) (w,(())T b,)()
m
rES,
[1,r,(A + 1) - (x)12 + (b, + 1) - (x:)
Vm
31

---

Under review as a conference paper at ICLR 2023
n E(B(+) - (k))r
11
n ar
> (1)(K) - u/ I (b:)
Or
+
m
Vm
mm
rES.
5m1
2
j=1
27
Σ
[53(k)) زز
m
rES, jml
20 S
[lf(k) - 2112
m
1/ llf(k) ull S m00((R + Ro) exp((BB/22) - v112 (6)
= +|ell2
m²
where we apply Corollary A.5 in the last inequality. To bound the first term,
Σ
ar (A: + 1) 24 6, - 1)) (k) xt (k)]
Vm rES;
1
(k)) ((ws + 1) - wx)k)) (b. 1) - bx))))
rES.
T
((-7
n (Jz(K) Uo )r)
Σ (kk)
(()(K) - U3 Ur)
"
m
(Tm
Vm
ar
Di
m
Gr
rES.
j=1
Σ (kk)
(-mma ar ((s(k) (1),
m
Vm
rES.
Σ j=1
(F)(k) - -U3) - Σ (k)))))r(((((()))))) x; +1
rES.
Σ (Jz(k) Uj) 1 Σ (40
7
Σ
(Us(k) 23) 25) Hiy (1:) +
J=1
j=1
rES,
<()
where we can upper bound (k))
2m
2
1<(k)]= S
[k)) vı S
[[f(k) -11/2
m
m
(8)
1 [f(kk) 21l2 < mn + Rb) exp(-B² [lf(k) v112.
+ ||e'112
m²
Combining Equation
Equation o Equation
and Equation
have
+ filk + - fikk)) n > (b,(K) (((() + (k:)
+ f(k - f(k) = (n)())((())))))
+v)) (kk() - +)
= =-nH> (f(k) - +)) - (F())) - y) + +
<(H)
k-1
S(()) - (1- -1- - -1) + Σ (1 2 1-
1=
-11-n11 + n11 + Σ (1 -1-1
c(k)
32

---

Under review as a conference paper at ICLR 2023
Now the rest of the proof bounds the magnitude of e(k).. From Lemma A.2 and Lemma A.6 have
|1 Hkk]l2 S (| - 1111112 + (1 (
112
=0 (1exp(-B²/44) log(n"/0) /0)
+nnnRR + exp(=
m
Thus, we can bound ((k) as
[k)) S 11 - (k))l [lf(k) - 1112 + ||E(H))12 + (1E((K)
=0 mm axp(-BB/44) log(n22/0 /6) + (Rw + Ro) exp(-B3 (B212) lf((k) - y112 /2)
m
Notice that || 1| v Tr(Hx)) & n since H is symmetric. By Theorem A.18 we pick = O(An²²) < 1/ H ||, and, with probability at least 1 - - Q())) over the random initialization,
we have [K( 2|ا2 (1 r///4) ([((0) yll2-
Since we are using symmetric initialization, we have (I - 00 f(0) = 0. Thus,
1
[|e(k)]l2
Σ 111
1
|| ~ 11((k: 1 t)ll2
mm (xp(-BB/4) log(n2/8)
(Rw + exp( B²/ /2)
I|[ t) -yll2
m
exp(- B2/4)/ log(n2/8) m
Σ (1 mm
+ (Rw + exp(xx2(B2
(1 12/4)(x-1-0)1 (1f(0) - vll2
< k(1 m0 exp(-B²/4)) log(n2/0)
+ (Rw + Rs) exp(-B²/2) llf(0) - vll2
< k(1 (k 1/) 1m120 2xp(-BB//4)
log(n2/8)
(Ry + Ro) exp(-
(V 1 (exp(-13//2) + 1/m) log" (2mm/8))
log(n2/8)
= k(1 - 11/88*-11 (xxp(B2//4)
+ (Ra + Rs) cxp(c
m
Lemma C.8. Assume the parameter settings in Theorem
A.18
Then with probability at least
5 (2(m) over the random initialization, we have for all
K
2 0,
exp( Hxp(-Bi B2 (2))))(((/))) 1/4)
W. (1)) [W.][0)]] I VUT -
n
A
my
+0
n + 0
(exp(- (xxp(-B//4)
log(n2 (n² (n2/8)
log
R Rexp(- -B²/2)
x
33

---

Under review as a conference paper at ICLR 2023
where R= Ruw Rs-
Before we start, we assume all the events needed in Theorem A.18 succeed, which happens Proof.
with probability at least - 6 - e e-2(x)
vec([W,]((K)) - vec (e, b)())
K-1 veo([W, 6]( + 1)) ([]
k=0
(kk)(u(k)) v)
((I - n1H -
K
nZ())(1 1
Σ (Z(k)((k)
K-1
K-1
nZ(0)(1 - -111)(1-1110001) +
n(((k) m1110)
Σ (k)e((() (9)
Ts
T3
Now, by Lemma A.6 we have 1Z( 7(0)1l S On B2)2)) which implies
K-1
12
Σ
(Z(k)) - -
K=
Σ n O(NnRx(((BB)))) || 11 12 |1y/|2
K-1
$ n -WVneexp-BBB//
Σ
(1 - T/aaa'
k=0
=0 " Re/Repp-PPP -B2/22
(10)
A
By |2(k)]2 |Z(b]lr S /2ni we get
K-
[Tall2
(k())((A))
K=U
log(n2/8 Rexp(-B²
k:1 2 2n
11//8)=11m1* (xxp-BB/4))
1og(n2/0)
exp(-B3 /4)
+ R Reexp--B2/2)
(11)
X2
m
Define T 1, D DIKI1 (I ) By Lemma
A.2
know
[[ -
11
cxp (BB -B2/4) log(n/6) and this implies
|
Σ
(2(0)(1 - 1H
k=0
=|1Z(0Tyyl3
34

---

Under review as a conference paper at ICLR 2023
yy TZ(O) y Z(0YTy
- y TH + 1 (0) - H 12 11711 llvl2
S y TH
n nx 1-2 (B2/4) log(n//))
R-1
Σ k=0
(1-=)))*)
(1
2
"
n² eepppp22/p (B2/BB
log(n/8) m
TH +
X²
- = UEUT T be the eigendecomposition. Then
K-1
T= U
Σ (I -
-U- -U((-(1-)))))--11
k=0
+ TH*T = U((I - (I - -1
=
= (HO0-1
Thus,
1771/2
k=
n12 exp( (B3/4)
1og(n/0)
11 (Hx))-y++
X2
m
V (H (exp(- 13 /2) log(n/6) 1/4
(12)
m
Finally, plugging in the bounds in Equation 9 have
Equation
12
Equation
10 and Equation
I[W, ()) - (W,)(())l= ([j) vec([W, b(()))12
exp((= log(mn/0) 1/0) )
VV (H O
ny R Rexp(- - -B²/2)
+0
log(n? (22/2) /5)
0 (exp(-B²//) x2
m + R Rexp(-B2212
D PROBABILITY
Lemma D.1 (Bernstein's Inequality). Assume Zı...., Zn are i.id random variables with
E|Z = 0 and |2,| < M for all i [m] almost surely. Let Z = - Z, Then, for all t >> 0,
1/2
t2
2M ))
t
P(Z > 1 S
exp
< exxp -mn
E[Z + Mt/3
2 2 EIZ
which implies with probability least 8,
<
2
E E| log
+ 2M log
5
3 1=1
35

---

Under review as a conference paper at ICLR 2023
Lemma D.2 (Matrix Chernoff Bound, (Tropp et al. 2015 ). Let X1...., Xm = be inde- pendent random Hermitian matrices. Assume that =
X; I L for some L > and for all
2 E [m]. Let X >i X,. Then, for e (0, 1], we have
IP [AAmin (X) S <Amin [E] [[[]]]] S n exp(-(1 - Amin Ami (22))
Lemma D.3 (Li & Shao 2001 Theorem 3.1) with Improved Upper Bound for Gaussian)). Let b > 0 and r > 0. Then,
1 (xx(-(max(
exp(-b2/22
F [|w] S <r]
<
P 1 bl [ 2r
(1011
w=,(0.1)
V
Proof.
To prove the upper bound, we have
P |kr | - bl sr] J.
htt 1 exp(pxx 12) dx S 2r
1
exp( (0m(0-(mmbbbb r, 0))
W va. W>
bbr 2
V2T
Lemma D.4 (Amti-cooncentaation of Gaussian). Let Z ~ (O0 o²). Then for 1> 0.
21.
2|
Σ t <
v VTT
E THE BENEFIT OF CONSTANT INITIALIZATION OF BIASES
In short, the benefit of constant initialization of biases lies in inducing sparsity in activation and thus reducing the per step training cost. This is the main motivation of our work on studying sparsity from deep learning theory perspective. Since our convergence shows that sparsity doesn't 't change convergence rate, the total training cost is also reduced.
To address the width's dependence set up neural network models by first picking a neural network of some pre-chosen size and then choose other hyper-parameterss such as learning rate, initialization scale, etc. In our case, the hyper- parameter is the bias initialization. Thus, the network width is picked before B. Let's say we want to apply our theoretical result to guide our practice. Since we usually don't know the exact data separation and the minimum eigenvalue of the NTK, we don't 't have good estimate on the exact width needed for the network to converge and generalize. We may pick network with width that is much larger than needed (e.g. we pick a network of width ((n22) whereas only 2(x²²) is needed; this is possible because the smallest eigenvalue of NTK can range from [2(1/n2 O(1)). Also, an empirical observation that the neural networks used in practice are very overparameterized and there is always room for sparsification. If the network width is very large, then per step gradient descent is very costly since the cost scales linearly with width and can be improved to scale linearly with the number of active neurons if done smartly. If the bias is initialized to zero (as people usually do in practice), then the number of active neurons is (m). However, since can sparsify the neural network activation by non-zero bias initialization, the number of active neurons can scale sub-lineerly in m. Thus, if the neural network width we choose the beginning is much larger than needed, then we are indeed able to obtain total training cost reduction by this initialization. The above is an informal description of the result proven in (Song et al.) (201a)) and the message is spar- sity can help reduce the per step training cost. If the network width is pre-chosen, then the lower bound on network width m 2 22
B, our argument goes like follows. In practice people
- nn' cxp (B)) in Theorem 3.1 can be translated into an upper
bound on bias initialization: < Ō(V log priate interpretation of our result. Note that this is different from how Theorem 3.1 is presented: first pick B and then choose m;; since m is picked later, can always satisfy B < v0.5 log and m 2 00xx=* n exp(B²)). Of course, we don't know the best (largest) possible B that works but as long as we can get some B to work, we can get computational gain from sparsity.
Xmm ne if m 2 A((77)=*) This would be a more appro-
reduce the per step training cost since we don't know the exact width needed for the network to converge and generalize. Our result should be interpreted as an upper bound on B since the width is always chosen before B in practice.
In summary, sparsity
36


Reviews:
[{"review_id": "vqDwCcoWR82", "reviewer": "Reviewer_neAa", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": " This paper studies the convergence and generalization of shallow ReLU networks with trainable bias’s initialized to a constant value.  They provide a global convergence guarantee and a local Rademacher complexity based generalization bound.\n", "summary_of_the_review": "This work attempts to address an interesting topic (the relation between sparse activations and optimization/generalization).  However the type of sparsity they study (initializing bias's to a large contant) feels contrived and is not justified.  Furthermore, I have doubts about the contribution of their work in relation to prior works.  If the authors can provide strong responses to my reservations which show that I missed essential components of their work I will consider raising my recommendation.  However, for now I am issuing a reject recommendation.", "strength_and_weaknesses": "**Strengths:**\nThis paper attempts to relate sparsity of activation patterns to the optimization and generalization of ReLU networks.  I do believe that sparsity of activation patterns in relation to the optimization dynamics and generalization is indeed an interesting topic that deserves study.\n\n**Weaknesses:**\nWhile I do think sparsity of activations is an interesting topic in relation to optimization and generalization, I think the sparsity studied in this present work is unnatural. Initializing the bias’s to some large constant value is not done in practice, and this work does not make an effort justify this form of initialization to induce sparsity.  While they cite [1] which considers this setting, I think this work should try to justify this to the reader on its own.  The number of neurons required by Theorem 3.1 is super-exponential in the bias initialization value $B$, and the convergence rate and step size decay super-exponentially with $B$.  Thus inducing sparsity by setting $B$ to be large comes at a high cost, and this must at least be explained.\n\nIn Theorem 3.1 the requirement on the width $m$ has quadratic dependence on $n$ similar to Theorem 2.3 in [2] (the arxiv version is the one I’m referencing).  The main difference I can see is that in [2] the network does not have bias’s.  My question to the authors is aside from training the bias’s what is the novelty in Theorem 3.1?\n\nTheorem 3.8 appears to be an adaption of Theorem 5.1 in [3].  I do not see what is different here aside from the modification to the NTK that comes from the specific bias initialization.  Also it does not seem that [3] is properly referenced in Theorem 3.8 (also note that the result in [3] is an instantiation of Lemma 22 in [4]).\n\nTheorem 3.11 is essentially outlining a sufficient condition on the labels so that the quantity $y^T (H^\\infty)^{-1} y$ is well bounded.  However this data dependent region they define seems quite arbitrary.  $y^T (H^\\infty)^{-1} y$ can be viewed as the discrete RKHS norm of the target function.  Improved optimization and generalization for target functions that have small RKHS norm has been investigated in [5] and [6].\n\nIn sum, I am not convinced about the contribution of the results of this work in relation to previous works.  The authors emphasize repeatedly that they improve over the results of [1], however I am not convinced that they significantly improve over the works I outline above.  If the authors can provide strong responses to my objections specifying the improvements of their works in relation to these works I will consider changing my recommendation.  However, for now I am inclined to issue a reject recommendation for this submission.\n\n**References:**\n\n[1] Zhao Song, Shuo Yang, and Ruizhe Zhang. Does preprocessing help training over-parameterized neural networks? Advances in Neural Information Processing Systems, 34:22890–22904, 2021a.\n\n[2] Samet Oymak and Mahdi Soltanolkotabi.  Towards moderate overparameterization: global convergence guarantees for training shallow neural networks.  Published in: IEEE Journal on Selected Areas in Information Theory, 1(1):84–105, 2020.\nPreprint: https://arxiv.org/pdf/1902.04674.pdf\n\n[3] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322–332. PMLR, 09–15 Jun 2019a. URL https://proceedings.mlr.press/v97/arora19a. html.\n\n[4] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3(null):463–482, mar 2003. ISSN 1532-4435.\n\n[5] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=HygegyrYwH.\n\n[6] Lili Su and Pengkun Yang. On learning over-parameterized neural networks: A functional approximation perspective. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alche-Buc, E. Fox, and ´ R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper/2019/file/ 253f7b5d921338af34da817c00f42753-Paper.pdf.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "NYQuN4Knze", "reviewer": "Reviewer_dzEj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This is a theoretical paper on an NTK analysis of two-layer ReLU network with a trainable nontrivial initial bias. The motivation of study is that by using an appropriately initialized bias term, the network produces *sparse* activation at initialization; and if one considers the kernel regime then the sparsity is maintained throughout training, hence may be leveraged for efficiency purposes (but this application is not the focus of this paper). \n\nThe main contributions are:\n\n- A convergence analysis to show that GD drives training error towards zero;\n- A generalization analysis to show generalization bound via Rademacher complexity;\n- (On a technical level) A new bound on the smallest eigenvalue of limiting NTK, by resorting to a \"data-dependent region\".", "summary_of_the_review": "The paper studies the important problem of sparse activation using a testbed of two-layer neural network in the NTK regime. The presentation is mostly good but there may be some missing discussions. The technical novelty seems a bit weak (though I am not familiar with related studies).", "strength_and_weaknesses": "# Strength\n\nSparsity in activation is becoming increasingly important as the size of the models we are training are becoming very large and resource-consuming to use. Existing theoretical study on networks with sparse activations seem rare, and this work may motivate many subsequent studies along this direction, potentially providing justification or guidance for introducing sparse activation in large models in more principled ways.\n\nThe paper is very well written and is easy to follow despite that it contains a lot of theoretical formulations and claims. Though certain relevant discussions seem missing.\n\nThe theoretical results on generalizatoin, convergence, and smallest eigenvalue seems interesting. (Though I am not in a position to understand their significance / novelty on a technical level)\n\n# Weakness\n\nTwo major questions I have:\n\n- Section 3.1 is structured as first presenting the main result (i.e., Theorem 3.1), then explains the key ideas of proving this result and some lemmas along the way. Here, I am not understanding how these lemmas lead to Theorem 3.1.\n\nSpecifically, Thm 3.1 is about training loss decaying to zero. Lemma 3.3 is about bounding activation flipping probability when the change in network parameter is not too large. However, I don't see a discussion on 1) why we expect the change in parameter is not too large, and 2) what is the benefit of bounding the activation flipping probability. Then, Lemma 3.4 provides an error bound on initial loss L(0), but there is no discussion on why we need to bound it given that we only need to bound the ratio L(t) / L(0).\n\n- The paper is about sparsity in activation maps, but there is in general a lack of discussion on 1) how / whether sparsity helps or provides benefits with proving the convergence / generalization results, and 2) how / whether sparsity facilitates convergence / improves generalization by their theoretical results, and whether such results aligns with what can be observed in practice (e.g. faster convergence and better generalization).\n\nOther comments:\n\n- Theorem 3.1: Maybe I missed it but I did not find where delta on the RHS of the inequality is defined.\n\n- Remark 3.2: Is the improvement over Song et al. obtained because this paper considers trainable bias while Song et al. considers non-trainable bias?\n\n- Definition 3.10: Data-dependent Region. This assumption is the key for the third contribution, but it seems quite arbitrary in the sense that we don't know if or how likely it is going to be satisfied in practice.\n\n# Additional Comments\n\nThere are some references on sparse activation in existing network architectures. These are particularly relevant as their sparsity emerges automatically from regular training.\n\n- Rhu, Minsoo, et al. \"Compressing DMA engine: Leveraging activation sparsity for training deep neural networks.\" 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA). IEEE, 2018.\n- Andriushchenko, Maksym, et al. \"SGD with large step sizes learns sparse features.\" arXiv preprint arXiv:2210.05337 (2022).\n- Li, Zonglin, et al. \"Large Models are Parsimonious Learners: Activation Sparsity in Trained Transformers.\" arXiv preprint arXiv:2210.06313 (2022).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IRmY3SFR-A", "reviewer": "Reviewer_D4Qh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyses 1 layer ReLU nets with trainable biases under a fixed bias init using the NTK framework. It polishes the proof techniques used in various other papers and gives better bounds for the overparameterisation required to be in the NTK regime. ", "summary_of_the_review": "Despite my issues listed in the weakness section, I think the paper makes enough technical contributions and proof technique ideas to merit an acceptance. \n\nThe paper would do very well to motivate why any practitioner would want a constant non-zero bias init both empirically and theoretically.", "strength_and_weaknesses": "Strengths:\n\nThe paper generalises classic NTK results to the trainable bias setting which is the standard setting for several training protocols. \n\nThe paper gives short and simple proof sketches to get the gist of the proof.The proof sketches do a good job of capturing the main technical novelty/contribution in the paper.\n\nCareful analysis and development of new proof techniques to get better bounds.\n\n\nWeaknesses:\n\n1. Trainable biases with non-constant/random init can easily be modelled with no-bias results using modified data with a concatenated constant to the feature vector. What advantage does constant bias init have over this init? This needs to be made clear.\n\n2. The advantage of a non-zero B initialisation seems non-existent in all the theoretical results -- Theorem 3.1 requires a larger net, and achieves slower convergence with a non-zero B when compared to B=0. The first (and more dominant) term of Rademacher complexity in Theorem 3.8 is independent of B as mentioned in the para after the theorem. Similarly in Theorem 3.11 using a non-zero B seems to only reduce the smallest eigen value. So why should one bother with this initialisation at all?\n\n3. The definition of \"data-dependent region\" is confusing. What is the Probabilitiy in definition of P_{ij} over? \n\n4. The experimental results for different initial biases is underwhelming and incomplete. Why not give results for positive B that would actually increase the number of inactive neurons?  In the experiments here the non-zero biases seem to increase the active neurons, while actually reducing the accuracy. \n\n5. It is also not clear which of the three main theorems the experimental result demonstrates. Perhaps it demonstrates a key property exploited by the Theorems, in which case this needs to be stated as a separate theorem.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AL5rebH-ML2", "reviewer": "Reviewer_crhr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers optimization and generalization properties one-hidden-layer ReLU networks trained in the NTK regime, with an initialization of the bias that is fixed to a non-zero constant $B \\geq 0$. This leads to networks with sparse activation patterns, which may be useful for sparsifying network parameters after training. The authors also provide improved bounds on width and generalization compared to previous works studying the NTK regime in similar settings, and complement the theory with simple experiments illustrating the sparsity of activations.", "summary_of_the_review": "The technical contributions are potentially useful, but the motivation is unclear.", "strength_and_weaknesses": "Strenghts: The tighter bounds on width and generalization seem to apply regardless of the sparsity level and could be a useful addition to the NTK literature.\n\nWeaknesses:\n\nI have trouble understanding the motivation behind this work: in the NTK regime, using a different initialization of the bias basically corresponds to using a different activation, namely a shifted ReLU $\\sigma(\\cdot - B)$ instead of $\\sigma$. While this may lead to sparser activation patterns, the width required to achieve similar guarantees to the $B = 0$ case (in the kernel regime at least) needs to be much larger, basically compensating the possible sparsity benefits.\n\nIt is also unclear if the use of a different activation requires an entirely new analysis, as opposed to using previous results. For instance, the bounds on least singular values of the kernel matrix have been tightly characterized in various settings with generic activations, e.g. [here](https://arxiv.org/abs/2007.12826) in certain high dimensional regimes. In particular, such statistical properties typically depend on Hermite coefficients of the activation, and for the shifted ReLU it should be easy to see that these are more or less scaled down by a factor $\\sim e^{-B^2/2}$ compared to the ReLU coefficients.\n\nThat said, I might have missed the motivation of the authors, and encourage them to explain this further. If the key contribution is about improving the bounds, then I'm not sure activation sparsity should be part of the story?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject