Title: STABILITY AND CONVERGENCE THEORY FOR LEARN-ING RESNET: A FULL CHARACTERIZATION

Abstract: ResNet structure has achieved great success since its debut. In this paper, we study the stability of learning ResNet. Specifically, we consider the ResNet block
)) where φ(•) is ReLU activation and τ is a scalar. We show that for standard initialization used in practice, τ = 1/Ω( √ L) is a sharp value in characterizing the stability of forward/backward process of ResNet, where L is the number of residual blocks. Specifically, stability is guaranteed for τ ≤ 1/Ω( √ L) while conversely forward process explodes when τ > L -1 2 +c for a positive constant c. Moreover, if ResNet is properly over-parameterized, we show for τ ≤ 1/ Ω( √ L) gradient descent is guaranteed to find the global minima 1 , which significantly enlarges the range of τ ≤ 1/ Ω(L) that admits global convergence in previous work. We also demonstrate that the over-parameterization requirement of ResNet only weakly depends on the depth, which corroborates the advantage of ResNet over vanilla feedforward network. Empirically, with τ ≤ 1/ √ L, deep ResNet can be easily trained even without normalization layer. Moreover, adding τ = 1/ √ L can also improve the performance of ResNet with normalization layer.

1. INTRODUCTION:

Residual Network (ResNet) has achieved great success in computer vision tasks since the seminal paper (He et al., 2016) . Moreover, the ResNet structure has also been extended to natural language processing and achieved the state-of-the-art performance (Vaswani et al., 2017; Devlin et al., 2018) . In this paper, we study the forward/backward stability and convergence theory of learning ResNet. Specifically, we consider the ResNet with the following residual block,

EQUATION

where φ(•) is the ReLU activation, h l is the output of layer l, W l is the parameter of layer l and τ is a scale factor on the parametric branch in a residual block. We note that standard initialization schemes, e.g., the Kaiming's initialization, are designed to keep the forward and backward variance constant when passing through one layer. However, things become different for ResNet. If W l adopts Kaiming's initialization, a small τ is necessary for a stable forward process of ResNet, because the output explodes in expectation for τ = 1 when L gets large. On the other side, a limit form of Euler's constant indicates that τ = 1/Ω(L) is sufficient for the forward stability as shown in previous work (Allen-Zhu et al., 2019; Du et al., 2019) . It is natural to ask "Are there other values of τ that can guarantee the stability of ResNet with arbitrary depth?"

We target the above question and unveil that τ = 1/ √ L is a sharp value in terms of characterizing the stability of forward/backward process of ResNet with a non-asymptotic analysis. Specifically, stability is guaranteed for τ ≤ 1/Ω( √ L). Conversely, for τ > L -1 2 +c the network output grows at least with rate L c in expectation, which implies forward/backward explosion for large L.

One step further, based on the stability argument, we show that if the network is properly overparameterized, gradient descent is guaranteed to find global minima for training ResNet with τ ≤ 1/ Ω( √ L), where the range of τ is significantly enlarged compared to the result in Allen-Zhu et al. (2018b) ; Du et al. (2018) with τ ≤ 1/Ω(L). Over-parameterization has been recently used as a hammer to tackle the optimization property (Allen-Zhu et al., 2018b; Du et al., 2018; Zou et al., 2018; Zou and Gu, 2019) of neural network. It considers the case when the neural network is very wide at each layer, which enables the theoretical analysis via the statistical concentration property of the parameter matrix. We show that the over-parameterization requirement of ResNet only weakly depends on the depth, which justifies the advantage of ResNet over feedforward network. Our contribution can be summarized as follows.

• We establish a non-asymptotic analysis showing that τ = 1/ √ L is tight in the order sense for characterizing the stability of ResNet.

• For τ ≤ 1/Ω( √ L log m), we establish the convergence of gradient descent to global minima for learning over-parameterized ResNet with arbitrary depth.

The key step to prove our first claim is a new bound of the spectral norm of the forward process for ResNet with τ ≤ 1/Ω( √ L). This bound is a bit surprising as a natural bound (1 + 1/ √ L) L explodes. We use martingale theory to characterize the largest possible change after multiple residual mappings, which is shown to be bounded given τ < 1/

√:

L. This technique may be of independent interest for other problems.

The idea for proving global convergence is as follows. First we establish the forward/backward stability at the initialization and derive the gradient upper/lower bounds by utilizing the statistical concentration of random matrix. Then we show the gradient bounds do not change much after perturbation as long as the perturbation is relatively small. Finally by properly choosing the step size, gradient descent update indeed produces small enough perturbation. Besides the forward/backward stability, the key step to show our global convergence is a new gradient upper bound which is tighter than previous works by exploiting the scaling factor τ . This new upper bound enables the weak depth-dependent argument of learning ResNet.

We note that although the global convergence of gradient descent for learning ResNet has been established by Allen-Zhu et al. (2018b) ; Du et al. (2018) for τ = 1/ Ω(L), if we train practical ResNet with τ = 1/L, the performance is largely worse than ResNet with normalization layer that is used in practice. In contrast, our stability and convergence theory can serve as a guide for practice. Empirically, we demonstrate that with τ = 1/ √ L, ResNet can be effectively trained without the normalization layers. Moreover, even with normalization layer, deep ResNet does not perform well in practice. We illustrate the reason from the stability perspective and demonstrate that adding τ = 1/ √ L on top of the normalization layer can obtain considerable performance improvement.

1.1. RELATED WORKS:

A concurrent work Arpit et al. (2019) considers a similar residual mapping and suggests that τ = 1/ √ L can keep the norm of the forward/backward pass roughly constant in expectation. In sharp contrast, we consider the standard initialization scheme used in practice and provide rigorous non-asymptotic analysis for the stability for the forward/backward pass with τ = 1/Ω( √ L). Zhang et al. (2019a) demonstrates that ResNet can be trained without normalization layer if the first mapping in a residual block is initialized down by 1/

L and the last mapping is initialized to 0. In contrast, our result shows that τ = 1/

L is sufficient for training a standard ResNet without normalization layer and achieve better empirical performance than Zhang et al. (2019a) . Zhang et al. (2019b) argues that a small τ can give robust ResNet from a partial differential equation interpretation of ResNet but does not provide how small τ should be. Moreover, our paper is also related to the work that have studied the benefit of ResNet (Veit et al., 2016; Zhang et al., 2018; Hardt and Ma, 2016; Orhan and Pitkow, 2018) .

Our paper is closely related to recent work on over-parameterization/neural tanget kernel (NTK) technique. The NTK approach considers the case when the neural network is very wide (often more neurons than samples) at each layer and the training iterates fall into a small region near the initialization. Jacot et al. (2018) ; Allen-Zhu et al. (2018b) ; Du et al. (2018) ; Chizat and Bach (2018) ; Zou et al. (2018) ; Zou and Gu (2019) ; Arora et al. (2019a) ; Oymak and Soltanolkotabi (2019) showed that gradient descent converges linearly to the global minima for training over-parameterized deep neural network from the optimization perspective. Brutzkus et al. (2017) ; Li and Liang (2018) ; Allen-Zhu et al. (2018a) ; Arora et al. (2019b) ; Cao and Gu (2019); Neyshabur et al. (2019) establish the generalization properties of over-parameterized neural network. On the other side, Ghorbani et al. (2019) ; Chizat et al. (2019) ; Yehudai and Shamir (2019) ; Allen-Zhu and Li (2019) discuss the limitation of the NTK approach in characterizing the behavior of neural network. The "limitation" lies in that kernel approach cannot approximate a single ReLU neuron efficiently and the empirical generalization gap between the NTK approach and neural network, which does not underrate our contribution as we focus on the convergence behavior of gradient descent. Moreover, our stability result on the range of τ holds beyond the NTK regime.

1.2. PAPER ORGANIZATION:

The rest of this paper is organized as follows. Section 2 introduces the model and notations. Section 3 gives a non-asymptotic analysis on the forward/backward stability of ResNet for a full range of τ . Section 4 presents the global convergence of gradient descent for training over-parameterized ResNet, including the proof roadmap. Section 5 gives some experiments that support our theory. Finally, we conclude in Section 6.

2. PRELIMINARIES:

There are many residual network models since the seminal paper (He et al., 2016) . Here we study a simple ResNet model with Kaiming's initialization (He et al., 2016) is described as follows2 ,

• Input layer:

h 0 = φ(Ax); • L -1 residual layers: h l = φ(h l-1 + τ W l h l-1 ); • A fully-connected layer: h L = φ(W L h L-1 ); • Output layer: y = Bh L ; • Initialization: A ∈ R m×p , B ∈ R d×m and W l ∈ R m×m for l = [L] where entries of A, B

and W l are independently sampled from N (0, 2 m ), N (0, 2 d ) and N (0, 2 m ), respectively; where φ(•) is the ReLU activation function φ(•) := max{0, •}. Specifically, we assume the input dimension is p and hence x ∈ R p , the intermediate layers have the same width m, and hence h l ∈ R m for l = 0, 1, ..., L, and the output has dimension d and hence y ∈ R d . Denote the values before activation by g 0 = Ax, g l = h l-1 + τ W l h l-1 for l = 1, 2, ..., L -1 and g L = W L h L-1 . Use h i,l and g i,l to denote the value of h l and g l , respectively, when the input vector is x i , and D i,l the diagonal sign matrix where

[D i,l ] k,k = 1 {(g i,l ) k ≥0} .

We introduce a notation -→ W := (W 1 , W 2 , . . . , W L ) to represent all the trainable parameters. Throughout the paper, we use v to denote the l 2 norm of the vector v. We further use M 2 and M F to denote the spectral norm and the Frobenius norm of the matrix M , respectively. Denote

-→ W 2 := max l∈[L] W l 2 and W [L-1] 2 := max l∈[L-1] W l 2 . The training data set is {(x i , y * i )} n i=1

, where x i is the feature vector and y * i is the target signal for all i = 1, ..., n. We consider the objective function is

F ( -→ W ) := n i=1 Fi( -→ W ), where Fi( -→ W ) := (Bhi,L, y * i ),

where (•) is the loss function that measures the discrepancy between the the network output and the target signal. The model is trained by running the gradient descent algorithm. Though ReLU is nonsmooth, we abuse the word "gradient" to represent the value computed through back-propagation.

3. FORWARD AND BACKWARD STABILITY OF RESNET:

In this section, we establish the stability of training ResNet. We show that when τ ≤ 1/Ω( √ L) the forward and backward pass is bounded at the initialization and after small perturbation. On the converse side, if τ > L -0.5+c for any positive constant c, the output norm grows at least polynomial with depth. The stability result has good correspondence with empirical observation. Moreover, it forms the basis for establishing the global convergence in Section 4.

3.1. FORWARD:

PROCESS IS BOUNDED FOR τ ≤ 1/Ω( √ L)

We first give a non-asymptotic bound on the spectral norm of the forward process at initialization.

Theorem 1. Suppose that -→ W (0) , A are randomly generated as in the initialization step, and D 0 , . . . , D L are diagonal matrices such that D l 2 ≤ 1 for all l ∈ [L] and D l is deterministic given {W (0) a : a ≤ l}. If τ ≤ 1/Ω( √ L), then there exists some small constant c such that with probability at least 1 -L 2 • exp(-Ω(mc 2 )) over the initialization randomness we have for any b > a,

EQUATION

The above result is a bit surprising since for τ = 1/Ω( √ L) a natural bound on the spectral norm

(I + τ W (0) L ) • • • (I + τ W (0) 1 ) ≤ (1 + 1 √ L ) L explodes.

Here the intuition is that the cross-product term concentrates on the mean 0 because of the independent randomness of matrices W (0) l . Moreover, we note that to guarantee Theorem 1 holds for all training samples [n], we take the union bound and the probability becomes 1 -nL 2 • exp(-Ω(mc 2 )). Next we give a rigorous argument based on the martingale sequence.

Proof Outline. Suppose we have h a-1 = 1. Then we abuse notations g l = h l-1 + τ W (0) l h l-1 and h l = D l g l for a ≤ l ≤ b, and we have

h b 2 = h b 2 h b-1 2 • • • h a 2 h a-1 2 h a-1 2 ≤ g b 2 h b-1 2 • • • g a 2 h a-1 2 h a-1 2 .

Taking logarithm at both side, we have

log h b 2 ≤ b l=a log ∆ l , where ∆ l := g l 2 h l-1 2 .

If let hl-1 := h l-1 h l-1 , then we obtain that

EQUATION

EQUATION

l hl-1 + τ 2 W (0) l hl-1 2 ,

where the inequality is because log(1 + x) < x for x > -1. Let ξ l := 2τ hl-1 , W

l hl-1 and

ζ l := τ 2 W (0) l hl-1 2 , for given hl-1 , ξ l ∼ N 0, 8τ 2 m , ζ l ∼ 2τ 2 m χ 2 m .

Without rigor, we could say

b l=a ξ l ∼ N 0, 8(b-a)τ 2 m and b l=a ζ l ∼ 2(b-a)τ 2 m χ 2 m .

Hence we have b l=a log ∆ l ≤ c with probability at least 1 -exp(-Ω(m)c 2 ). Taking ε-net argument, we can establish the spectral norm bound for all vector h a-1 . Let a and b vary from 1 to L -1 and taking the union bound gives the claim.

We next show that the output norm at each layer is close to 1. Theorem 2. Suppose τ ≤ 1/Ω( √ L). There exists some small constant c such that with probability at least 1 -O(nL) • e -Ω(m•min(c,c 2 )) over the randomness of A ∈ R m×p and -→

W (0) ∈ (R m×m ) L the following holds ∀i ∈ [n], l ∈ {0, 1, . . . , L} : h (0) i,l ∈ [1 -c, 1 + c].

(3)

The proof is relegated to Appendix C.1. We note that Theorem 2 is much stronger compared with the result in Allen-Zhu et al. (2018b) which is only showed for the case τ = 1/Ω(L log m). Moreover the above two lemmas also holds for -→ W that is within the neighborhood of -→ W (0) and the result is presented in Appendix C.2.

In the sequel, c is treated as a fixed constant, e.g. c = 0.1, which may be hidden in the Ω() or O() notation.

3.2. BACKWARD PROCESS IS BOUNDED:

FOR τ ≤ 1/Ω( √ L)

For ResNet, the gradient with respect to the parameter is computed through back-propagation, e.g., ∂W l = ∂h l • h T l-1 , where ∂• represents the gradient of the objective with respect to •. Therefore, the gradient upper bound is guaranteed if h l and ∂h l are bounded across layers and iterations. We next show the backward process is bounded for each individual sample.

Theorem 3. With probability at least 1 -(nL) • exp(-Ω(m)) over the randomness of -→ W (0) , A, B, it satisfies for every l ∈ [L -1], every i ∈ [n], and every

-→ W with -→ W - -→ W (0) 2 ≤ ω for ω ∈ [0, 1], ∇ W l F i ( -→ W ) 2 F ≤ O F i ( -→ W ) d × τ 2 m , ∇ W L F i ( -→ W ) 2 F ≤ O F i ( -→ W ) d × m . (4)

The full proof is relegated to Appendix D.1. Here we give an outline.

Proof Outline. The argument is based on the bounded forward/backward process at -→ W and the back-propagation formula. For each i ∈ [n] and l ∈ [L -1], i.e., the residual layers, we have

∇ W l Fi( -→ W ) F = τ D i,l (I + τ W l+1 ) T • • • Di,L-1W T L Di,LB T (Bhi,L -y * i ) h T i,l-1 ≤ O(τ m/d) Fi( -→ W ),

where the last inequality is due to that the forward/backward process is bounded for all the

-→ W such that -→ W - -→ W (0) 2 ≤ ω (Lemma 3 in Appendix).

This gradient upper bound indicates that the gradient of residual layers could be much (τ < 1) smaller than the usual feedfoward layer.

3.3. A CONVERSE RESULT:

FOR τ > 1/Ω( √ L)

We have built the stability of the forward/backward process for τ ≤ 1/Ω( √ L). We next establish a converse result showing that if τ is slightly larger than 1/Ω( √ L), the network output norm grows uncontrollably as the depth L increases, which justifies the tightness of the value τ = 1/Ω( √ L) for arbitrary L.

Theorem 4. For the ResNet defined and initialized as in Section 2, if τ ≥ L -1 2 +c , then in expectation

EQUATION

Proof. The proof is relegated to the supplemental material in Appendix G.

This indicates the value of τ = 1/Ω( √ L) is tight for characterizing the forward stability of learning ResNet. We note that the theoretical results in Section 3 hold for very mild condition i.e., high probabiltiy is obtained when m > Ω(log(nL)). In the next section, we will show that gradient descent is guaranteed to find the global minima for training ResNet if the network is properly over-parameterized when τ ≤ 1/Ω( √ L).

Up to now, we have provided a full characterization of the ResNet stability in terms of the value of τ . Next, we take one step further towards bridging the theory to practice. We study whether this theoretical result has any practical guide. In practice, instead of using τ , the normalization layers, e.g. batch normalization (BN) and layer normalization (LN), are used to control the forward/backward stability. One first guide is that ResNet can be effectively trained even without normalization layer if choosing τ = 1/ √ L, as shown in the experiments in Section 5.

Our experiments demonstrate that the training performance of ResNet with τ is on par with the ResNet with BN for all depths {20, 32, 56, 110, 1202} on CIFAR10 classification task. The test performance is a bit complicated: ResNets with τ drop 1 ∼ 2 points compared to ResNet with BN for depths {20, 32, 56, 110} , which may be attributed to the regularization effect of BN (Zhang et al., 2019a) ; for depth 1202, ResNet with τ is slightly better than ResNet with BN. This motivates us to study the potential benefit of combining BN and τ .

We observe that although the residual block output norm of ResNet with BN does not increase exponentially, it still increases as traversing through layers. We give an heuristic estimation on how the residual block output norm grows for ResNet with BN. Take the image classification task as an example, the input is normalized across channel and batch. Therefore, for (g l ) k = BN ((W l h l-1 ) k ), we assume that Var[(g l ) k ] = 1 for all k = 1, ..., m and l = 0, 1, ..., L -1. We further assume the independence of each (g l ) k . Then, we have the following estimation.

Claim 

4. GRADIENT DESCENT CONVERGES TO GLOBAL MINIMA FOR LEARNING OVER-PARAMETERIZED RESNET:

In this section, we establish that gradient descent can converge to global minima for learning overparameterized ResNet with τ ≤ 1/Ω( √ L). Compared to the recent work (Allen-Zhu et al., 2018b) , our result enlarges the region of τ that admits the global convergence of gradient descent. Moreover, our result also theoretically justifies the advantage of ResNet over vanilla feedforward network in terms of facilitating the convergence of gradient descent. Before stating the theorem, we introduce a common assumption on the training data (Allen-Zhu et al., 2018b; Zou and Gu, 2019; Oymak and Soltanolkotabi, 2019) .

Assumption 1 (training data). For any x i , it holds that x i = 1 and (x i ) p = 1/ √ 2. For every pair i, j ∈ [n], we assume x i -x j ≥ δ.

We further assume that the loss function (•, •) is quadratic and the objective function for individual sample becomes

F i ( -→ W ) := 1 2 Bh i,L -y * i 2 .

Theorem 5. Suppose that the ResNet is defined as in Section 2 with τ ≤ 1/Ω( √ L log m) and training data satisfy Assumption 1. If the network width m ≥ Ω(n 8 L 7 δ -4 d log 2 m), then with probability at least 1 -exp(-Ω(log 2 m)), gradient descent with learning rate η

= Θ( d nm ) finds a point F ( -→ W ) ≤ ε in T = Ω(n 2 δ -1 log n log 2 m ε ) iterations.

Proof. The proof is deferred to Appendix F. Moreover, we argue that even for τ = 1/Ω( √ L log m), the depth dependence for learning overparameterized ResNet is smaller than that for learning feedforward network, which is also better than the bound for ResNet given in previous work (Allen-Zhu et al., 2018b) . This theoretically justifies the advantage of ResNet over vanilla feedforward network in terms of facilitating the convergence of gradient descent. For the case of τ ≤ 1/Ω(L log m), the depth dependence might be further reduced at the cost of adding the order on n. We believe that the depth dependence of ResNet is due to the limit of bounding techniques when handling nonsmooth activation. Better bounding technique or smooth activation function may help remove such dependence. We leave this for future study. For the case of τ > 1/Ω( √ L), the global convergence cannot be guaranteed because of the instability of the forward process for extremely large depth as shown in Section 3.3.

4.1. PROOF SKETCH AND MAIN CHALLENGES:

Though the objective is nonconvex and nonsmooth from the first sight, it admits good optimization property, which can guarantee the convergence of gradient descent, at the initialization and along the optimization path. Specifically, we establish three properties in the neighborhood of initialization: gradient is upper bounded, gradient is lower bounded, i.e., the gradient is large when the objective is large, and the objective satisfies certain smooth property.

The gradient upper and lower bounds for each individual sample have been proved based on the stability of forward/backward process at the initialization stage and after small perturbation in Section 3.2. Then following Allen-Zhu et al. (2018b) ; Zou and Gu (2019) , we argue the sum of individual gradients also being large. The gradient lower bound is presented as Theorem 7 in Appendix D.2.

The next challenge is to establish the objective smoothness. We present an informal semismoothness3 result. Interestingly, from this result, we can illustrate the advantage of learning ResNet: the convergence of learning ResNet only depends on the network depth weakly, echoing the empirical evidence that deep ResNet is much easier to train than deep feedforward network. Theorem 6 (Informal semi-smoothness result). Let ω < 1 and τ 2 L ≤ 1. With high probability, we have for every

- → W ∈ (R m×m ) L with W L -W (0) L 2 ≤ ω and W l -W (0) l 2 ≤ τ ω for l ∈ [L-1], and for every -→ W ∈ (R m×m ) L with W L 2 ≤ ω and W l 2 ≤ τ ω for l ∈ [L -1], we have F ( - → W + -→ W ) ≤F ( - → W ) + ∇F ( - → W ), -→ W + O nm d -→ W 2 F + O mnLω 2/3 d (τ L) 4/3 -→ W F F ( - → W ).

We note that apart from the second-order term (the third term on the right hand side) in classical smoothness, the semi-smoothness has a first-order term (the last term on the right hand side). One can see that as m becomes large in the over-parameterization regime the effect of the first-order term becomes small comparing to the second-order term. Interestingly, if one replaces W L and W l with the gradient upper bounds in Theorem 3, only the first-order term depends on L while the second-order term, which is dominant when m is large, is depth-independent. We note that the first-order term is the only source where the depth dependence in Theorem 5 comes from, which renders the depth dependence is weak for learning ResNet when m is large, in contrast with the case of learning deep feedforward network (Allen-Zhu et al., 2018b) .

5. EMPIRICAL STUDY:

In this section, we present some experiments to verify our theory. We first demonstrate that τ = 1/ √ L is a sharp value in determining the trainability of deep ResNet. We then show that practical ResNet with τ can be efficiently trained even without normalization layer. We finally show for ResNet with normalization, that adding τ also achieve considerable performance gain for both CIFAR and ImageNet tasks.

5.1. THEORETICAL VERIFICATION:

We train feedforward fully-connected neural networks and ResNets with different values of τ , and compare their convergence behaviors. The feedforward model adopts the same architecture and initialization scheme as the ResNet model except the skip connection (see Section 2). The models are generated with width m = 128 and depth L ∈ {3, 10, 30, 100, 500, 1000} and . We conduct experiments with τ = 1 L , 1 L 0.5 , 1 L 0.25 and show how it affects the training performance. We use MNIST dataset (LeCun et al., 1998) and do the classification task. We train the model with SGD4 and the size of minibatch is 256. The learning rate lr is set as lr = 0.001 without heavily tuning.

Experiment results. We plot the training curves of feedforward network and ResNet with varying depths and widths in Figure 1 . We see that both τ = 1 L and τ = 1 L 0.5 are able to train very deep ResNets successfully. However, when τ = 1 L 0.25 , the training loss explodes for models with depth 30

Under review as a conference paper at ICLR 2020 and more. This indicates that the bound τ = 1 √ L is sharp for learning ResNet with arbitrary depth. Moreover the convergence of ResNets with τ = 1 L and τ = 1 L 0.5 do not depend on the depth much while training feedforward network becomes harder as the depth increases, which verifies our theory of weak dependence on depth for learning ResNet. 

5.2. LEARN RESNET WITH τ:

We use more experiments to demonstrate that ResNet can be trained efficiently with τ even when there is not normalization layer.

In this section we conduct experiments on CIFAR10/100 datasets. We use the ResNet models (He et al., 2016) with the same hyperparameters but remove all the normalization layers. Motivated by Zhang et al. (2019a) , we add learnable scalar bias at the input of each convolution layer. Moreover, we treat τ as a learnable parameter with initialization 1/ √ L. Following Zhang et al. (2019a) , the learning rate of scalar parameters is divided by 10. All blocks share the same τ and we use the averaged gradient to update τ . Figure 2 shows the training/validation curves. With τ initialized as 1 √ L , we can easily train ResNet without batch normalization (BN) even for very deep networks. We note that Zhang et al. (2019a) has also proposed a way to train ResNet without normalization layers by doing specific initialization strategy (scaling down the first weight matrix and zeroing the last weight matrix inside all residual blocks). We compare the performances of our τ ResNet strategy and the Fixup scheme in Table 1 . From Table 1 , we see that scaling down the output of residual block has better performance than scaling down the initialization. Moreover, the Fixup scheme fails to converge 2 out of 5 runs for training ResNet1202 while there is no failure case for our τ ResNet. This indicates that the Fixup scheme could be unstable for extremely deep ResNet. The possible reason is that τ can stabilize both the forward pass and the backward pass while scaling down initialization only stabilizes the forward pass.

We also conduct experiments on Transformer (Vaswani et al., 2017) for machine translation task and compare our τ and the Fixup scheme Zhang et al. (2019a) . Transformer uses multiple residual connections in its basic building block. Therefore multiplying τ after each residual connection can also stabilize its training process. The results is relegated to Appendix H. 

5.3. ADD τ ON TOP OF NORMALIZATION:

In this section, we investigate the property of ResNet model with normalization layer and empirically demonstrate that adding a τ on top of normalization can achieve even better performance.

We first illustrate how the output norm of each residual block grows for ResNet1202 with BN (He et al., 2016; Ioffe and Szegedy, 2015) in Figure 3 . We see that at epoch 0 (initialization stage), the output norm grows almost at the rate √ l as we estimate in Claim 1. After training, the estimation in Claim 1 is not as accurate as the initialization because the independence assumption does not hold after training. Nonetheless, by adding a τ on top of BN, the output norm keeps roughly constant across the forward layers and across the training epochs.

We next verify that adding τ can further improve the performance over original models.

Experiments on image classification. We use the standard classification datasets: CIFAR10/100 and ImageNet. Our models and hyperparameters are the same as in He et al. (2016) . The only modification is multiplying a fixed τ = 1 √ L at the output of each residual block (right before the residual addition). For ResNet1202, we do not use small learning rate to warm up the training. The validation errors on CIFAR10/100 are illustrated in Figure 4 , where all numbers are averaged over five runs. We note that the benefit of τ becomes larger when the network is deeper. Without τ , the performance of ResNet1202 on CIFAR10 is worse than ResNet110 as shown in He et al. (2016) . As depth increases, the norm grow and imbalance over layers hurts the performance, which covers up the benefit of adding layers. As shown in Figure 4 , ResNets+BN+τ keep the output norm roughly constant and make good use of the network depth.

The ResNet model for ImageNet has different numbers of residual blocks in each stage, and we choose L to represent the largest number of blocks over all stages. We choose τ = 2 √ L for ImageNet dataset. All models are trained for 200 epochs with learning rate divided by 10 every 60 epochs. The other hyperparameters are the same as in He et al. (2016) .

Table 2 shows the results on ImageNet. We can see that by just adding a τ on top of BN we can achieve considerable performance gain. We note that a trick in Goyal et al. (2017) that initializes the scaling factor γ of the last BN of each residual block to 0, shares the same spirit as a small τ here, but does not have principled justification. 

6. CONCLUSION:

In this paper, we provide a non-asymptotic analysis on the forward/backward stability for ResNet, which unveils that τ = 1/ √ L is a sharp value in terms of characterizing the stability. Furthermore, when the network is properly over-parameterized, we show that gradient descent finds global minima for training ResNet with τ ≤ 1/Ω( √ L log m) which greatly improves over previous work of τ ≤ 1/Ω(L log m). We also bridge theoretical understanding and practical guide of ResNet structure. We empirically verify the efficacy of the suggestion τ = 1/ √ L for ResNet with/without batch normalization. One interesting future direction is to bypass the semi-smooth argument and give a sharp dependence on the depth and the number of training samples.

A USEFUL LEMMAS:

First we list several useful bounds on Gaussian distribution. Lemma 1. Suppose X ∼ N (0, σ 2 ), then

EQUATION

)

EQUATION

)

Another bound is on the spectral norm of random matrix (Vershynin, 2012, Corollary 5.35 ). Lemma 2. Let A ∈ R N ×n , and entries of A are independent standard Gaussian random variables.

Then for every t ≥ 0, with probability at least 1 -exp(-t 2 /2) one has

EQUATION

where s max (A) are the largest singular value of A.

B SPECTRAL NORM BOUND AT INITIALIZATION:

Next we present a spectral norm bound related to the forward process of ResNet with τ .

Theorem 1. Suppose that -→ W (0) , A are randomly generated as in the initialization step, and D 0 , . . . , D L are diagonal matrices such that D l 2 ≤ 1 for all l ∈ [L] and D l is deterministic given {W (0) a : a ≤ l}. If τ ≤ 1/Ω( √ L), then there exists some small constant c such that with probability at least 1 -L 2 • exp(-Ω(mc 2 )) over the initialization randomness we have for any b > a,

EQUATION

Proof. We first show for any vector h a-1 with h a-1 = 1, we have h b ≤ 1 + c with high probability, where

EQUATION

Using notations g l = h l-1 + τ W l h l-1 introduced in Section 2, we have g l ≥ h l . Thus we have the following

h b 2 = h b 2 h b-1 2 • • • h a 2 h a-1 2 h a-1 2 ≤ g b 2 h b-1 2 • • • g a 2 h a-1 2 h a-1 2 .

Taking logarithm at both side, we have

EQUATION

)

If let hl-1 := h l-1 h l-1 , then we obtain that

log ∆ l = log 1 + 2τ hl-1 , W (0) l hl-1 + τ 2 W (0) l hl-1 2 ≤ 2τ hl-1 , W (0) l hl-1 + τ 2 W (0) l hl-1 2 ,

where the inequality is due to the fact log(1 + x) ≤ x for all x > -1.

EQUATION

)

Next we bound terms on the right hand side one by one. For the first term we have

EQUATION

)

where λ is any positive number and the last inequality uses the Markov's inequality. Moreover,

EQUATION

Hence we obtain

EQUATION

by choosing λ = mc 32τ 2 l and τ ≤ 1/Ω( Then, for the second term, we first present a concentration inequality for the general χ 2 m distribution X (Laurent and Massart, 2000, Lemma 1)

EQUATION

Then for b l=a ζ l , by applying the above concentration inequality and Jensen's inequality, we have

EQUATION

Combining equation 16, equation 14 and the condition τ ≤ 1 Ω( √ L) , we obtain h b ≤ 1 + c with probability at least 1 -exp(-Ω( mc 2 τ 2 L )), where we use approximation log(1 + c) ≈ c for small c to simplify the expression. Taking -net over all m-dimensional vectors of h a-1 , with probability 1 -exp(-Ω(mc 2 )) the inequality 2 holds for a fixed a and b with 1 ≤ a ≤ b < L. Taking a union bound over a and b, the conclusion is proved.

The -net argument is as follows. We have proved for a given unit vector h a-1 , h b > 1 + c with probability at most exp(-Ω( mc 2 τ 2 L )) for a small constant c. Let N be an ε-net over the unit ball in R m with = 1/11, then we have the cardinality |N | ≤ (1 + 2/ ) m < (23) m . Taking the union bound over all vectors h a-1 in the net N , we obtain

P max ha-1∈N h b > 1 + c ≤ (1 + 2/ ) m • exp -Ω mc 2 τ 2 L = exp -m Ω( mc 2 τ 2 L ) -log 23 .

By choosing the coefficient of τ appropriately, we can make Ω( mc 2 τ 2 L ) > log 23 and then the right hand side can be written as exp -m -Ω( mc 2 τ 2 L ) . Based on the result (Vershynin, 2012, Lemma 5. 3), we have

D b I + τ W (0) b D b-1 • • • D a I + τ W (0) a 2 ≤ (1 -) -1 max ha-1∈N h b 2 = 1.1 max ha-1∈N h b 2 .

We complete the -net argument for the spectral norm bound by introducing a new constant c.

C BOUNDED FORWARD/BACKWARD PROCESS C.1 PROOF AT INITIALIZATION:

Theorem 2. Suppose τ ≤ 1/Ω( √ L). There exists some small constant c such that with probability at least 1 -O(nL) • e -Ω(m•min(c,c 2 )) over the randomness of A ∈ R m×p and -→

W (0) ∈ (R m×m ) L the following holds ∀i ∈ [n], l ∈ {0, 1, . . . , L} : h (0) i,l ∈ [1 -c, 1 + c].

(3)

Proof. We ignore the subscript (0) for simplicity. The upper bound of h i,l can be easily achieved by the proof of Theorem 1. Now, we give the lower bound of h i,l . First we have

EQUATION

)

Then we see

EQUATION

where ∆ a := hi,a 2 -hi,a-1 2 hi,a-1 2 and the last inequality uses the relation log(1 + x) ≥ x -x 2 . We next give a lower bound on ∆ a . Let S be the set {k

: k ∈ [m] and (h i,a-1 ) k + (W a h i,a-1 ) k > 0}.

We have that

EQUATION

)

where the inequality is due to the fact that for k / ∈ S,

|(h i,a-1 ) k | < |(τ W a h i,a-1 ) k | and (h i,a-1 ) k (W a h i,a-1 ) k ≤ 0. We let ξ a := 2τ hi,a-1,W a hi,a-1 hi,a-1 2 and ζ a := τ W ahi,a-1 2 hi,a-1 2

, then

∆ a ≥ ξ a -ζ a . We note that given h i,a-1 , ξ a ∼ N 0, 8τ 2 m and ζ a ∼ 2τ 2 m χ 2 m .

Due to equation 14 and equation 16, we have

EQUATION

Then for any c > 0, and τ ≤ 1 Ω( √ L) , we have

P l a=1 ∆ a ≤ -c = P l a=1 ∆ a ≤ -c, l a=1 ξ a ≥ - c 2 + P l a=1 ∆ a ≤ -c, l a=1 ξ a ≤ - c 2 ≤ P l a=1 ζ a ≥ c 2 + P l a=1 ξ a ≤ - c 2 = e -Ω(c 2 m) .

(21) We can derive a similar result that P l a=1 ∆ a ≥ c ≤ e -Ω(c 2 m) . Let a = b in equation 20, we obtain that for a single ∆ a ,

P (|∆ a | ≥ c) ≤ 2e -Ω(Lmc 2 ) (22)

In addition, we see that

EQUATION

)

Thus, similar to the equation 21, we obtain

EQUATION

which results in

EQUATION

)

Then we get the conclusion.

C.2 LEMMAS AND PROOFS AFTER PERTURBATION:

We use -→ W (0) to denote the weight matrices at initialization and use -→ W to denote the perturbation matrices. Let

-→ W = -→ W (0) + -→ W . We define h (0) i,l = φ((I + τ W (0) l )h (0) i,l-1 ) and h i,l = φ((I + τ W l )h i,l-1 ) for l ∈ [L -1], and h (0) i,L = φ(W (0) L h (0) i,L-1 ) and h i,L = φ(W L h i,L-1 ). Furthermore, let h i,l := h i,l -h (0) i,l and D i,l := D i,l -D (0)

i,l . Then the spectral norm bound after perturbation is as follows. Lemma 3. Suppose that -→ W (0) , A are randomly generated as in the initialization step, and D 0 , . . . , D L are diagonal matrices such that D l 2 ≤ 1 for all l ∈ [L] and D l is deterministic given {W (0) a : a ≤ l}, and W 1 , . . . , W L ∈ R m×m are perturbation matrices with W l 2 < τ ω for all l ∈ [L -1] for some ω < 1. Then with probability at least 1 -(L) • exp(-Ω(m)) over the initialization randomness we have

EQUATION

)

Proof. This proof is based on the result of Theorem 1. From Theorem 1, we know for any 1 ≤ a ≤ b < L

(I + τ W (0) b )D b-1 • • • D a (I + τ W (0) a ) 2 ≤ 1 + c. Then we have (I + τ W (0) b + τ W b )D b-1 • • • D a (I + τ W (0) a + τ W a ) 2 ≤ b-a+1 j=0 b -a + 1 j τ W j (1 + c) j+1 ≤ (1 + c) • (1 + (1 + c)τ 2 ) b-a+1 ≤ O(1 + c), due to the assumption W l ≤ τ ω for l ∈ [L -1] and ω < 1, τ ≤ 1/Ω( √ L).

We also have small changes on the output vector of each layer after perturbation. Lemma 4. Suppose for

ω ≤ O(1), τ 2 L ≤ 1, W L 2 ≤ ω and W l 2 ≤ τ ω for l ∈ [L -1].

Then with probability at least 1 -exp(-Ω(mω 2 /3 )), the following bounds on h i,l and D i,l hold for all i ∈ [n] and all l ∈ [L -1],

h i,l ≤ O(τ 2 Lω), D i,l 0 ≤ O m(ωτ L) 2/3 , h i,L ≤ O(ω), D i,L 0 ≤ O mω 2/3 .

Proof. Fixing i and ignoring the subscript in i, by Claim 8.2 in Allen-Zhu et al. (2018b) , for l ∈ [L -1], there exists

EQUATION

We claim that

EQUATION

due to the fact D l 2 ≤ 1 and the assumption W l 2 ≤ τ ω for l ∈ [L -1]. This implies that h i,l , g i,l ≤ O(τ 2 Lω) for all l ∈ [L -1] and for all i with probability at least 1 -O(nL) • exp(-Ω(m)). One step further, we have h L , g L ≤ O(ω).

As for the sparsity D l 0 , we have

D l 0 ≤ O(m(ωτ L) 2 /3 ) for every l = [L -1] and D L 0 ≤ O(mω 2 /3 ).

The argument is as follows (adapt from the Claim 5.3 in Allen-Zhu et al. (2018b) ).

We first study the case for l ∈ [L -1]. We observe that if (D l ) j,j = 0 one must have

|(g l ) j | > |(g (0) l ) j |.

We note that (g

(0) l ) j = (h (0) l-1 + τ W (0) l h (0) l-1 ) j ∼ N (h (0) l-1 ) j , 2τ 2 h (0) l-1 2 m . Let ξ ≤ 1 2 √ m be a parameter to be chosen later. Let S 1 ⊆ [m] be a index set satisfying S 1 := {j : |(g (0) l ) j | ≤ ξτ }. We have P{|(g (0) l ) j | ≤ ξτ } ≤ O(ξ √ m) for each j ∈ [m]

. By Chernoff bound, with probability at least 1 -exp(-Ω(m 3/2 ξ)) we have

|S 1 | ≤ O(ξm 3/2 ).

Let S 2 := {j : j / ∈ S 1 , and (D l ) j,j = 0}. Then for j ∈ S 2 , we have |(g l ) j | > ξτ . As we have proved that g l ≤ O(τ 2 Lω), we have

|S 2 | ≤ g l 2 (ξτ ) 2 = O((ωτ L) 2 /ξ 2 ). Choosing ξ to minimize |S 1 | + |S 2 |, we have ξ = (ωτ L) 2 /3 / √ m and consequently, D l 0 ≤ O(m(ωτ L) 2 /3 ). Similarly, we have D L 0 ≤ O(mω 2 /3 ).

We next prove that the norm of a sparse vector after the ResNet mapping.

Lemma 5. If s ≥ Ω(d/ log m) and τ ≤ 1/Ω( √ L), then for all i ∈ [n] and a ∈ [L] and for all s-sparse vectors u ∈ R m and for all v ∈ R d , the following bound holds with probability at least 1 -(nL) • exp(-Ω(s log m))

EQUATION

where D i,a is diagonal matrix with value 0 or 1 and it is independent of W b for any b ∈ (a, L].

Proof. For any fixed vector

u ∈ R m , D i,L W L D i,L-1 (I + τ W L-1 ) • • • D i,a (I + τ W a )u ≤ 1.1 u holds with probability at least 1 -exp(-Ω(m)) (over the randomness of W l , l ∈ [L]).

On the above event, for a fixed vector v ∈ R d and any fixed W l for l ∈ [L], the randomness only comes from B, then

v T BD i,L W L D i,L-1 (I + τ W L-1 ) • • • D i,a (I + τ W a )

u is a Gaussian variable with mean 0 and variance no larger than O( u

• v / √ d). Hence P |v T BD i,L W L D i,L-1 (I + τ W L-1 ) • • • D i,a (I + τ W a )u| ≥ s log m • Ω( u v / √ d) = erfc(Ω( s log m)) ≤ exp(-Ω(s log m)).

Take -net over all s-sparse vectors of u and all d-dimensional vectors of v, if s ≥ Ω(d/ log m) then with probability 1 -exp(-Ω(s log m)) the claim holds for all s-sparse vectors of u and all d-dimensional vectors of v. Further taking the union bound over all i ∈ [n] and a ∈ [L], the lemma is proved.

D GRADIENT LOWER/UPPER BOUNDS AND THEIR PROOFS:

Because the gradient is pathological and data-dependent, in order to build bound on the gradient, we need to consider all possible point and all cases of data. Hence we first introduce an arbitrary loss vector and then the gradient bound can be obtained by taking a union bound.

We define the BP-→ W ,i (v, •) operator. It back-propagates a vector v to the • which could be the intermediate output h l or the parameter W l at the specific layer l using the forward propagation state of input i through the network with parameter -→ W . Specifically,

BP-→ W ,i (v, h l ) := (I + τ W l+1 ) T D i,l+1 • • • (I + τ W L-1 ) T D i,L-1 W T L D i,L B T v, BP-→ W ,i (v, W l ) := τ D i,l (I + τ W l+1 ) T • • • (I + τ W L-1 ) T D i,L-1 W T L D i,L B T v h T i,l-1 ∀l ∈ [L -1], BP-→ W ,i (v, W L ) := D i,L B T v h T i,L-1 .

Moreover, we introduce

BP-→ W ( - → v , W l ) := n i=1 BP-→ W ,i (v i , W l ) ∀l ∈ [L],

where

- → v is composed of n vectors v i for i ∈ [n]. If v i is the error signal of input i, then ∇ W l F i ( -→ W ) = BP-→ W ,i (Bh i,L -y * i , W l ). D.1 GRADIENT UPPER BOUND Theorem 3. With probability at least 1 -(nL) • exp(-Ω(m)) over the randomness of -→ W (0) , A, B, it satisfies for every l ∈ [L -1], every i ∈ [n], and every -→ W with -→ W - -→ W (0) 2 ≤ ω for ω ∈ [0, 1], ∇ W l F i ( -→ W ) 2 F ≤ O F i ( -→ W ) d × τ 2 m , ∇ W L F i ( -→ W ) 2 F ≤ O F i ( -→ W ) d × m . (4) Proof. For each i ∈ [n], we have BP-→ W (v i , W L ) F = D i,L B T v i h T i,L-1 F = D i,L B T v i h T i,L-1 ≤ O( m/d) v i .

Similarly, we have for l

∈ [L -1], BP-→ W (v i , W l ) F = τ D i,l (I + τ W l+1 ) T • • • (I + τ W L-1 ) T D i,L-1 W T L D i,L B T v i h T i,l-1 ≤ O(τ m/d) v i .

The above upper bounds hold for the initialization -→ W (0) because of Lemma 1 and Lemma 2. They also hold for all the -→ W such that -→ W --→ W (0) 2 ≤ ω due to Lemma 4 and Lemma 3. Finally, taking -net over all possible vectors -→

v = (v 1 , . . . , v n ) ∈ (R d

) n , we prove that the above bounds holds for all -→ v . In particular, we can now plug in the choice of v i = Bh i,L -y * i and obtain the desired bounds on the true gradients.

D.2 GRADIENT LOWER BOUND:

Theorem 7. Let ω = O δ 3/2 n 3 log 3 m . With probability at least 1 -exp(-Ω(mω 2 /3 )) over the randomness of -→ W (0) , A, B, it satisfies for every

EQUATION

This gradient lower bound on ∇ W L F ( -→ W ) 2 F acts like the gradient dominance condition (Zou and Gu, 2019; Allen-Zhu et al., 2018b) except that our range on ω does not depend on the depth L.

Proof. The gradient lower-bound at the initialization is given in (Allen-Zhu et al., 2018b, Section 6.2 ) and (Zou and Gu, 2019, Lemma 4.1) via the smoothed analysis (Spielman and Teng, 2004): with high probability the gradient is lower-bounded, although the worst case it might be 0. We adopt the same proof for (Zou and Gu, 2019, Lemma 4.1) based on two preconditioned results Theorem 2 and Lemma 6. We shall not repeat it here.

Now suppose that we have:

∇ W L F ( -→ W (0) ) 2 F ≥ Ω F ( -→ W (0) ) dn/δ

× m . We next bound the change of the gradient after perturbing the parameter. Recall that

BP-→ W (0) ( - → v , W L ) -BP-→ W ( - → v , W L ) = n i=1 (v T i BD (0) i,L ) T (h (0) i,L-1 ) T -(v T i BD i,L ) T (h i,L-1 ) T

By Lemma 4 and Lemma 5, we know,

v T i BD (0) i,L -v T i BD i,L ≤ O( mω 2 /3 / √ d) • v i .

Furthermore, we know

v T i BD i,L ≤ O( m/d) • v i .

By Theorem 2 and Lemma 4, we have

h (0) i,L-1 ≤ 1.01 and h i,L-1 -h (0) i,L-1 ≤ O(ω).

Combing the above bounds together, we have

BP-→ W (0) ( - → v , W L ) -BP-→ W ( - → v , W ) 2 F ≤ n - → v 2 • O( mω 2 /3 /d + ω m/d) 2 ≤ n - → v 2 • O m d ω 2 /3

Hence the gradient lower bound still holds for

-→ W given ω < O δ 3/2 n 3 . Finally, taking -net over all possible vectors - → v = (v 1 , . . . , v n ) ∈ (R d

) n , we prove that the above gradient lower bound holds for all -→ v . In particular, we can now plug in the choice of v i = Bh i,L -y * i and it implies our desired bounds on the true gradients.

The gradient lower bound requires the following property. Lemma 6. For any δ and any pair (x i , x j ) satisfying x i -x j 2 ≥ δ, then h i,l -h j,l ≥ Ω(δ) holds for all l ∈ [L] with probability at least 1-O(n 2 L)•exp(-Ω(log 2 m)) for τ ≤ 1/Ω( √ L log m) and m ≥ Ω(τ 2 L 2 δ -2 ).

The proof of Lemma 6 follows that of (Allen-Zhu et al., 2018b, Appendix C.1) given the condition that m ≥ Ω(τ 2 L 2 δ -2 ).

E SEMI-SMOOTHNESS:

FOR τ ≤ 1/Ω( √ L)

With the help of Theorem 3 and several improvements, we can obtain a tighter bound on the semismoothness condition of the objective function.

Theorem 8. Let ω ∈ Ω d m log m 3 /2

, O(1) and -→ W (0) , A, B be at random initialization and τ 2 L ≤ 1. With probability at least 1 -exp(-Ω(mω 2 /3 )) over the randomness of -→ W (0) , A, B, we have for every

EQUATION

Before going to the proof of the theorem, we introduce a lemma.

Lemma 7. There exist diagonal matrices D i,l ∈ R m×m with entries in [-1,1] such that ∀i ∈

EQUATION

and

EQUATION

Furthermore, we then have ∀l ∈

[L -1], h i,l -hi,l ≤ O(τ 2 Lω), D i,l 0 ≤ O(m(ωτ L) 2 /3

), and

h i,L -hi,L ≤ O((1 + τ √ L) W F ), D i,L 0 ≤ O(mω 2 /3 ) and Bh i,L -B hi,L ≤ O( m/d) W F hold with probability 1 -exp(-Ω(mω 2 /3 )) given W L 2 ≤ ω, W l 2 ≤ τ ω for l ∈ [L -1] and ω ≤ O(1), τ √ L ≤ 1.

Proof. The proof can adapt from the proof of Claim 8.2 in Allen-Zhu et al. (2018b) and the proof of Lemma 4.

Proof of Theorem 8. First of all, we know that loss

EQUATION

and

EQUATION

)

EQUATION

Then,

EQUATION

where (a) is due to Lemma 7.

We next bound the RHS of equation 37. We first use Lemma 7 to get

EQUATION

Next we calculate that for l = L,

EQUATION

)

For the first term, by Lemma 5 and Lemma 7, we have

EQUATION

where the last inequality is due to h i,L-1 ≤ O(1). For the second term, by Lemma 7 we have

EQUATION

where the last inequality is due to the assumption W L 2 ≤ ω. Similarly for l ∈ [L -1], we ignore the index i for simplicity.

EQUATION

We next bound the terms in equation 42 one by one. For the first term, by Lemma 5 and Lemma 7, we have

EQUATION

where (a) is due to the similar argument in the proof Lemma 7 and the fact 1) and h l-1 = O(1) holds with high probability.

W L (D L-1 + D L-1 )(I + τ W L-1 ) • • • (D l + D l ) = O(

We have similar bound for the second term of equation 42

EQUATION

)

For the last term in equation 42, we have

EQUATION

)

where is the last inequality is due to the bound on h l-1 -hl-1 2 in Lemma 7. Hence

EQUATION

Having all the above together and using triangle inequality, we have the result.

Proposition 1 (Proposition 8.3 in in Allen-Zhu et al. (2018b) ). Given vectors a, b ∈ R m and D ∈ R m×m the diagonal matrix where D k,k = 1 a k ≥0 . Then, there exists a diagonal matrix D ∈ R m×m with

• |D k,k + D k,k | ≤ 1 and |D k,k | ≤ 1 for every k ∈ [m], • D k,k = 0 only when 1 a k ≥0 = 1 b k ≥0 , • φ(a) -φ(b) = (D + D )(a -b).

Proof of Lemma 7. Fixing index i and ignoring the subscript in i for simplicity, by Proposition 1, for each l ∈

[L -1] there exists a D l such that |(D l ) k,k | ≤ 1 and h l -hl = φ((I + τ W l + τ W l )h l-1 ) -φ((I + τ W l ) hl-1 ) = ( Dl + D l ) (I + τ W l + τ W l )h l-1 -(I + τ W l ) hl-1 = ( Dl + D l )(I + τ W l )(h l-1 -hl-1 ) + ( Dl + D l )τ W l h l-1 = l a=1 ( Dl + D l )(I + τ W l ) • • • (I + τ W a+1 )( Da + D a )τ W a h a-1

Then we have following properties. For l ∈

[L -1], h l -hl ≤ O(τ 2 Lω). This is because ( Dl + D l )(I + τ W l ) • • • (I + τ W a+1 )( Da + D a ) ≤ 1.1 from Lemma 3; h a-1 ≤ O(1) from Theorem 2; and the assumption W l 2 ≤ τ ω for l ∈ [L -1].

To have a tighter bound on h L -hL , let us introduce W

b := l a=b ( Dl + D l )(I + τ W l ) • • • (I + τ W a+1 )( Da + D a )W a , for b = 1, ..., l. Then we have h L -hL = W L , W L-1 , ..., W 1 [h T L-1 , τ h T L-2 , ..., τ h T 0 ] T . (47) It is easy to get [τ h T l-1 , τ h T l-2 , ..., τ h T 0 ] T 2 = τ 2 l-1 a=0 h a 2 ≤ τ √ L • O(1),

where the inequality is because of h a-1 ≤ O(1) from Theorem 2. Next, we have

EQUATION

where the second inequality is from the definition of spectral norm, the third inequality is because of

( Dl + D l )(I + τ W l ) • • • (I + τ a+1 )( Da + D a ) ≤ 1.1 from Lemma 3. Hence we have h L -hL ≤ O (1 + τ √ L) W F = O W F because of the assumption τ √ L ≤ 1. For l ∈ [L], D l 0 ≤ O(mω 2 /3

). This is because (D l ) k,k is non-zero only at coordinates k where (g l ) k and (g l ) k have opposite signs, where it holds either (D

(0) l ) k,k = ( Dl ) k,k or (D (0) l ) k,k = (D l ) k,k . Therefore by Lemma 4, we have D l 0 ≤ O(m(ωτ L) 2 /3 ) if W l 2 ≤ τ ω.

F PROOF FOR THEOREM 5:

Theorem 5. Suppose that the ResNet is defined as in Section 2 with τ ≤ 1/Ω( √ L log m) and training data satisfy Assumption 1. If the network width m ≥ Ω(n 8 L 7 δ -4 d log 2 m), then with probability at least 1 -exp(-Ω(log 2 m)), gradient descent with learning rate η = Θ( d nm ) finds a point F ( -→ W ) ≤ ε in T = Ω(n 2 δ -1 log n log 2 m ε ) iterations.

F.1 CONVERGENCE RESULT FOR GD:

Proof. Using Theorem 2 we have h

i,L 2 ≤ 1.1 and then using the randomness of B, it is easy to show that Bh (0) i,L -y * i 2 ≤ O(log 2 m) with probability at least 1-exp(-Ω(log 2 m)), and therefore

F ( -→ W (0) ) ≤ O(n log 2 m).

(49) Assume that for every t = 0, 1, . . . , T -1, the following holds,

W (t) L -W (0) L F ≤ ω ∆ = O δ 3/2 n 3 L 7/2 (50) W (t) l -W (0) l F ≤ τ ω.

(51) We shall prove the convergence of GD under the assumption equation 50 holds, so that previous statements can be applied. At the end, we shall verify that equation 50 is indeed satisfied.

Letting ∇ t = ∇F ( -→ W (t) ), we calculate that

EQUATION

where the first inequality uses Theorem 4, the second inequality uses the gradient upper bound in Theorem 3 and the last inequality uses the gradient lower bound in Theorem 7 and the choice of η = O(d/(mn)) and the assumption on ω equation 50. That is, after T = Ω( dn ηδm ) log n log 2 m iterations F ( -→ W (T ) ) ≤ .

We need to verify for each t, equation 50 holds. Here we use a result from (Zou and Gu, 2019, Lemma 4. 2) that states W ).

To guarantee the iterates fall into the region given by ω equation 50, we obtain a bound m ≥ n 8 δ -4 dL 7 log 2 m.

G TIGHTNESS OF τ = 1/ √ L AND THE PROOF OF THEOREM 4

Theorem 4. For the ResNet defined and initialized as in Section 2, if τ ≥ L -1 2 +c , then in expectation

E h L 2 > L 2c .

(5)

Proof. By we can show for any k ∈ [m] and l ∈ [L -1],

EQUATION

It is easy to verify (h

1 ) k = φ ((h 0 ) k + (τ W 1 h 0 ) k ) ≥ φ ((τ W 1 h 0 ) k ) because of (h 0 ) k ≥ 0.

Then assume (h l ) k ≥ φ l a=1 (τ W a h a-1 ) k , we show it holds for l + 1. where the last inequality can be shown by case study.

Next we can compute the mean and variance of l a=1 (τ W a h a-1 ) k by taking iterative conditioning. We have

EQUATION

)

Moreover, (τ W a h a-1 ) k are jointly Gaussian for all a with mean 0 because W a 's are drawn from independent Gaussian distributions. We use l = 2 as an example to illustrate the conclusion, it can be generalized to other l. Assume that h 0 is fixed. First it is easy to verify that (τ W 1 h 0 ) k is Gaussian variable with mean 0 and (τ W 2 h 1 ) k W 1 is also Gaussian variable with mean 0. Hence [(τ W 1 h 0 ) k , (τ W 2 h 1 ) k ] follows jointly Gaussian with mean vector [0, 0]. Thus (τ W 1 h 0 ) k + (τ W 2 h 1 ) k is Gaussian with mean 0. By induction, we have l a=1 (τ W a h a-1 ) k is Gaussian with mean 0. Then we have

EQUATION

)

where the first step is due to equation 53, the second step is due to the symmetry of Gaussian distribution and the third step is due to equation 54. Since (h l ) k = φ ((h l-1 ) k + (W l h l-1 ) k ), we can show E(h l ) 2 k ≥ (h l-1 ) 2 k given h l-1 by numerical integral of Gaussian variable over an interval. Hence we have E h l 2 ≥ E h l-1 2 ≥ • WMT EN-DE Transformer (Vaswani et al., 2017) 28.4 Fixup (Zhang et al. (2019a)) 28.1 Transformer + τ 29.1

Table 3 : Experiment results on machine translation task (Higher is better).

In this section, we train Transformer with τ but no normalization layer. We conduct experiments on two standard machine translation tasks: IWSLT DE-EN and WMT EN-DE. We modify the model by multiplying a fixed τ right after each residual addition and removing all the normalization layers. We do not use scalar bias in our Transformer+τ model. For IWSLT DE-EN, we adopt the Transformer-base model and set τ = 0.5. For WMT EN-DE, we use Transformer-big model and set τ = 0.3. Dropout is set as 0.5 for base model. For big model, we set attention dropout and activation dropout as 0.1. Other hyperparameters are the same as Vaswani et al. (2017) . For Fixup, we use the implementation by Zhang et al. (2019a) . All models are trained for 150 epochs with 25k batch size. We average the checkpoints of the last 10 epochs and evaluate the BLEU score. The scores are shown in Table 3 .

I EXTREME DEEP RESNET:

Per reviewer's request, we plot the training curves of extremely deep ResNets with the width m ∈ {8, 16} and the depth L ∈ {1000, 5000, 10000} in Figure 5 . We set τ = 1 L 0.5 . We see that even for ResNet with depth 10000 and width 8, the training curve although fluctuates, manages to converge. This reflects the depth dependency of ResNet is weak, echoing our stability result.

:

We use Ω(•) to hide logarithmic factor.

The same ResNet model has been used inAllen-Zhu et al. (2018b) andDu et al. (2018). Here, we borrow notations fromAllen-Zhu et al. (2018b).

The smoothness is compromised from the usual sense because of the non-smoothness of ReLU.

GD exhibits the same phenomenon. We use SGD due to the expensive per-iteration cost of GD.

Figures and Tables:

This theorem establishes the linear convergence of gradient descent for learning ResNet with τ ≤ 1/Ω( √ L log m). Compared with Allen-Zhu et al. (2018b); Du et al. (2018), our result significantly enlarges the range of τ (from τ ≤ 1/Ω(L log m) to τ ≤ 1/Ω( √ L log m)) that can guarantee the global convergence of training over-parameterized ResNet.

Figure 1: Training curves for feedforward network and ResNets with τ = 1 L , 1 L 0.5 and 1 L 0.25 (from left to right).

Figure 2: Experiment results on CIFAR10/100 with τ initialized as 1 √ L . All normalization layers are removed.

Figure 3: Output norm of ResNet1202 over layers at different epochs. X axis is the index of block. Y axis is the output norm ratio compared to the first block.

Figure 4: Top1 validation error on CIFAR10/CIFAR100 dataset. The benefit of τ becomes larger as network goes deeper.

L). Due to the symmetry of b l=a ξ l , the conclusion can be generalized to the quantity | b l=a ξ l |.

O( n 2 d log m mδ

h l+1 ) k = φ ((h l ) k + (τ W l+1 h l ) k ) ≥ φ φ l a=1 (τ W aha-1) k + (τ W l+1 h l ) k ≥ φ l+1 a=1 (τ W aha-1) k ,

Figure 5: ResNet with 1000/5000/10000 layers. The width is 8 for the left figure and 16 for the right.

The calculation can be adapted from the proof of Theorem 4. This indicates that the output norm of ResNet with BN grows roughly at the rate√L. We propose that adding τ = 1/ √ L on top of BN can keep the output norm roughly constant across layers, which produces considerable performance gain especially for deep ResNet.

Table content: <table/>

Top1 validation error on CIFAR10. Numbers are average of 5 runs except ResNet1202 + Fixup (standard deviations are given inside the bracket).

Table content: <table><tr><td/><td/><td/><td colspan="2">Dataset</td><td colspan="8">Depth ResNet + FixupInit ResNet + τ</td></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="2">20</td><td>8.72(±0.26)</td><td colspan="4">8.39(±0.11)</td></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="2">32</td><td>7.99(±0.24)</td><td colspan="4">7.68(±0.10)</td></tr><tr><td/><td/><td/><td colspan="2">CIFAR 10</td><td/><td colspan="2">56</td><td>7.45(±0.37)</td><td colspan="4">7.07(±0.16)</td></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="2">110</td><td>7.24(±0.12)</td><td colspan="4">6.52(±0.20)</td></tr><tr><td/><td/><td/><td/><td/><td colspan="3">1202</td><td>7.83(±0.18)</td><td colspan="4">6.08(±0.21)</td></tr><tr><td/><td/><td/><td>Epoch=0</td><td/><td/><td/><td/><td>Epoch=50</td><td/><td/><td/><td>Epoch=150</td></tr><tr><td>norm ratio</td><td>0 2 4 6 8 10 12 14 16 18</td><td>0</td><td>50 number of blocks 100 150 ResNet1202+BN ResNet1202+BN+ ResNet1202+ ResNet1202</td><td>200</td><td>norm ratio</td><td>0 2 4 6 8 10 12 14 16 18</td><td>0</td><td>50 number of blocks 100 150 ResNet1202+BN ResNet1202+BN+ 200 ResNet1202+</td><td>norm ratio</td><td>0 2 4 6 8 10 12 14 16 18</td><td>0</td><td>50 number of blocks 100 150 ResNet1202+BN ResNet1202+BN+ 200 ResNet1202+</td></tr></table>

Validation error on ImageNet dataset.

Table content: <table><tr><td>Model</td><td colspan="2">Method Validation Error (Top1)</td></tr><tr><td>ResNet50</td><td>+BN +BN+τ</td><td>23.6 23.0</td></tr><tr><td>ResNet101</td><td>+BN +BN+τ</td><td>22.0 21.4</td></tr><tr><td>ResNet152</td><td>+BN +BN+τ</td><td>21.7 20.9</td></tr></table>

Peer review (iclr2020):
The paper presents a non-asymptotic analysis of ResNet stability which determines a *cutoff* value for the residual block scale factor characterizing stability vs output explosion, and improves upon prior results by finding a larger range for the scale factor that lead to global convergence in non-convex optimization. Theoretical findings are corroborated via experiments confirming the validity of the *cutoff* value. Additional experiments are conducted indicating that using the cutoff value, ResNet can be trained even without normalization layers, and that the cutoff value is also beneficial with normalization as it allows effective training of very deep ResNet. This is an interesting submission which presents important theoretical results while also showing their practical pertinence via experimental validation. The paper is well written and the presentation is clear. Prior work is reviewed appropriately. The reviewer found it particularly informative to provide intuition and present a proof sketch next to each theoretical results. The convergence analysis leads to a depth dependence of ResNet and the authors claim that this is not a *real* dependence and attributes it to bounding techniques handling non smooth activation. The authors further indicate in their experiments that for a given width the convergence of ResNet does not depends *much* on depth, compared to feedforward networks. So there might still be a dependence though much milder than that found by the current theory. It would be interesting to more precisely characterize the dependence observed in experiments. The authors claim that their analysis leading to the non-asymptotic bound on the spectral norm of the feedforward process via martingale theory might be relevant for other problems. It would be useful if the authors could elaborate and in particular indicate if their technique could carry to analyse other structures beyond ResNet. Minor comments: *What else values* ---> Are there other values *our first claim is a new spectral norm* --> is a new bound of the spectral norm *we does no make such* --> we do not make