STABILITY AND CONVERGENCE THEORY FOR LEARNING RESNET: A FULL CHARACTERIZATION
Authors: Huishuai Zhang
Da Yu
Mingyang Yi
Wei Chen
Tie-yan Liu
Venue:  (2020)
Keywords: ResNet
stability
convergence theory
over-parameterization

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 $h_l = \phi(h_{l-1}+\tau\cdot g(h_{l-1}))$ where $\phi(\cdot)$ is ReLU activation and $\tau$ is a scalar. We show that for standard initialization used in practice, $\tau =1/\Omega(\sqrt{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 $\tau\le 1/\Omega(\sqrt{L})$ while conversely forward process explodes when $\tau>L^{-\frac{1}{2}+c}$ for a positive constant $c$.  Moreover,  if ResNet is properly over-parameterized, we show for $\tau \le 1/\tilde{\Omega}(\sqrt{L})$ gradient descent is guaranteed to find the global minima \footnote{We use $\tilde{\Omega}(\cdot)$ to hide logarithmic factor.}, which significantly enlarges the range of $\tau\le 1/\tilde{\Omega}(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 $\tau\le1/\sqrt{L}$, deep ResNet can be easily trained even without normalization layer. Moreover, adding $\tau=1/\sqrt{L}$ can also improve the performance of ResNet with normalization layer.

Under review as a conference paper at ICLR 2020
STABILITY AND CONVERGENCE THEORY FOR LEARN- ING RESNET: A FULL CHARACTERIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
ResNet structure has achieved great success since its debut. this paper, we study the stability of learning ResNet. Specifically, consider the ResNet block hy = 6(h-11 + T g(hx-1) where (6() is ReLU activation and t is a sealar. We show that for standard initialization used in practice, т = 1/52(VL) 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 S 1/9(vL) while conversely forward process explodes when -. for a positive constant c. Moreover, if ResNet is properly parameterizedd we show for S 1/$2(VL) gradient descent is guaranteed to find the global minima which significantly enlarges the range of r S 1/(((L) that admits global convergence previous work. We also demonstrate that the over-paramettrrizaton requirement of ResNet only weakly depends on the depth, which corroborates the advantage ResNet over vanilla feedforward network. Empirically, with т S I/VL, deep ResNet can be easily trained even without normalization layer. Moreover, adding T == 1/VT. can also improve the performance of ResNet with normalization layer.
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-arr 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,
h 6(h-1 + 7 rW ih1-1);
where (b-) is the ReLU activation, hy is the output of layer I, Wi is the parameter of layer and T is scale factor the parametric branch in residual block. We note that standard initialization schemes, e.g., the Kaiming's 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 adopts Kaiming's 's initialization, small 7 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, limit form of Euler's 's constant indicates that 7 1/52 L) is sufficient for the forward stability as shown in previous work (Allen Zhu et al. 2019 Du et al.) 2019). It is natural ask
"Are there other values of r that can guarantee the stability of ResNet with arbitrary depth?"
We target the above question and unveil that r = I/VL. is sharp value in terms of characterizing the stability of forward/backward process of ResNet with non non-asymptotic analysis. Specifically, stability is guaranteed for r S 1/S2(VI.. Conversely, for r > L- 1 +o the network output grows at least with rate L 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 over- parameterized, gradient descent is guaranteed to find global minima for training ResNet with r < 1/L(VVL) where the range of r is significantly enlarged compared to the result in Allen-Zhu et al.
We use 22-) to hide logarithmic factor.

---

Under review as a conference paper at ICLR 2020
(0188); Du et al. (2018) with S 1/Q(L). over-paaramtttiizaaiinn has been recently used hammer to tackle the optimization property (Allen-Zhi) 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 wver-parameterizttion 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/VL is tight in the order sense for characterizing the stability of ResNet.
For < VVV we establish the convergence of gradient descent to global minima for learning over-parameterizedd ResNet with arbitrary depth.
The key step to prove our first claim is new bound of the spectral norm of the forward process for ResNet with S 1 1/2(VVT. This bound is a bit surprising as a natural bound (1 + 1/VT.) explodes. We use martingale theory to characterize the largest possible change after multiple residual mappings, which is shown to be bounded given T < 1/vL. 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. 8201 Du et al. (2018) for T 1/L2(L), if we train practical ResNet with 7 = L, the performance largely worse than ResNet with normalization layer that is used in practice. In contrast, our stability and convergence theory can serve as guide for practice. Empirically, we demonstrate that with r = 1/VL, 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 T 1/VI 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 T = 1/VL 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/backwart pass with 1/S(VL)). Zhang et al. (2019a) demonstrates that ResNet can be trained without normalization layer the first mapping in a residual block is initialized down by 1/VT. and the last mapping is initialized to O. In contrast, our result shows that T = 1/VL is sufficient for training standard ResNet without normalization layer and achieve better empirical performance than Zhang al. (2019)) Zhang et al. (019b) argues that small can give robust ResNet from a partial differential equation interpretation of ResNet but does not provide how small J 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 peerpprraneterizzaionneeerr 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 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 miniaa for training over parameterized deep neural network from the optimization perspective. Brutzkus et al. (2017) Li and Liang (008))
2

---

Under review as a conference paper at ICLR 2020
Allen-Zhu al. (20 Sa): Arora al. (2019b): Cao and Gu (001)); Neyshabur et al. (2019) establish the generalization properties of over parameterized neural network. On the other side. Ghorbani al. (2019); Chizat et al. (2019); Ychudai and Shamir (2019); Allen-Zhu and Li (2019) discuss the limitation of the NTT approach in characterizing the behavior of neural network. The "limitation" lies in that kernel approach cannot approximate single ReLU neuron efficiently and the empirical generalization gap between the NTK approach and neural network, which does not underrate our contribution 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 introduces the model and notations. Section gives non-asymplotic analysis the forward/backwart stability of ResNet for full range of Section presents the global convergence of gradient descent for training over-parameterized ResNet, including the proof roadmap. Section gives some experiments that support our theory. Finally, we conclude in Section
PRELIMINARIES
There are many residual network models since the seminal paper (He al. 2016). Here we study simple ResNet model with Kaiming's 's initialization (He et al. 2016) is described as follows
Input layer: ho o(Ar);
L 1 residual layers: h4 = 6(h1-1 (hihi
A fully-connected layer: Jy @(W tht-1);
Output layer: y = BhL;
Initialization: A Rmxp, B E Raxm and W pmxm
xm for [L] where entries of A, B and W, are independently sampled from (0, _ N,,, 3) and (00, 2. respectively;
where of-) is the ReLU activation function <b.) max (0, +). Specifically, dimension is p and hence x E IR,, the intermediate layers have the same width m,, and hence hy E m for / 1, ..., L, and the output has dimension and hence y _R Denote the values before activation by 9o = Az, = f1-1 + +W 1/1-1 for = 1, .... L - 1 and gL W W Use h4 and 9i,1 denote the value of fu and gi respectively, when the input vector is H;, and D the diagonal sign matrix where [ DD,,lk, = ((m.))20)
assume the input
We introduce a notation W = (W 2 W 1.) to represent all the trainable parameters. Throughout the paper, we ||u|| denote the lo of the vector v. We further use || | || and [M to denote the spectral norm and the Frobenius norm of the matrix M, respectively. Denote [ = max Willa and || [1-1)]l2 max [ ll2.
The training data set is {(r; yt v()) where v; the feature vector and y is the target signal for all 1,... n. We consider the objective function
F(W) = Σ F(W), where F(W) = ((Bh.,,,)),
where f(-) 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 T S 1/S(vL) the forward and backward pass is bounded at the initialization and after small perturbation. On the
2 The same ResNet model has been used in Allen-Zhu et al. 2018h) and Du al. 2018). Here, we borrow notations from Allen-Zhu et al. 2018b)

---

Under review as a conference paper at ICLR 2020
converse side, if L-0.5+ for any positive constant the output grows least polynomial with depth. The stability result has good correspondence with empirical observation. Moreover, forms the basis for establishing the global convergence in Section
3.1 FORWARD PROCESS IS BOUNDED FOR T S 1/D(VT.)
We first give non-asymptotic bound on the spectral norm of the forward process at initialization.
Theorem 1. Suppose that W A are randomly generated as in the initialization step. and Do...., Dr are diagonal matrices such that [|Dill2 S for all I & [L] and Di is deterministic given (W()) a S 11. If I (/S(VL) then there exists some small constant e such that with probability at least _ expeexp((-Su exp((((mm=) over the initialization randomness we have for any > a,
Do (I ( Do-1.... Do (I (0
>|b s1+c.
(2)
The above result is a bit surprising since for 1/9(vL) natural bound on the spectral norm + .. (I++W S (1+ }² explodes. Here the intuition is that the cross-product
term concentrates the mean 0 because of the independent randomness of matrices W( Moreover, we note that to guarantee Theorem [ holdd for all training samples [n], we take the union bound and the probability becomes 1 nL2 exp(- (smm=))(m²)). Next we give rigorous argument based on the martingale sequence.
Proof Outline. Suppose have | 1. Then we abuse notations Øi h1-1 1 + -W 44-1
and h4 = Digi for a S S b, and we have
|1
| 1
119b 1|
11ga ||2 |a-
||
11a
11
|| ha- 111
| 1
1/6 |||
Taking logarithm at both side, we have
119 1|
log [1 1|? S
log A..
where A
11//111
If let hi-1 = h1-1 [ then we obtain that
log A log (1 2r (h--1, w hn-1) + 1 fm m1=1 S 2r ("
( m1-11??
where the inequality is because log(1 + x)) < x for x > -. Let Ei == 27 (hn-1, W hn-1) and
:== ? / 112 for given 14-1. E1 ~ N (0. 8r²
G ~ 2r² X
m
Without rigor, we could say Ei. & ~ N (0, 8íb-a).?
and Σi Se ~ 2(h=a)r²
Xm Hence we
have Σ log A S c with probability least 1 exp( (mmm²²) Taking s-net argument, we can establish the spectral norm bound for all vector ha-1- Let and b vary from I 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 7 S 1/D.VD). There exists some small constant c such that with probability
at least 1 O(nL) ((m-mine())))" over the randomness of A IR mxx and ( E (Rmxmyz. the following holds
Vi [n], 10, L):
(0)
E [1 c, +|.
(3)
The proof is relegated to Appendix C.I We note that Theorem is much stronger compared with the
result in Allen-Zhu al. (2018b) which is only showed for the case 1/92(L logm), m). Moreover
the above two lemmas also holds for W that is within the neighborhood of (² 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 2() or 0() notation.
4

---

Under review as a conference paper at ICLR 2020
3.2 BACKWARD PROCESS BOUNDED FOR S 1/2(VL)
For ResNet, the gradient with respect to the parameter is computed through back-propagation, e.g.. ow, Ohy h where O- represents the gradient of the objective with respect Therefore, the gradient upper bound is guaranteed if h2 and Ōh, are bounded across layers and iterations. We next show the backward process bounded for each individual sample.
Theorem 3. With probability at least 1 (nL) exp((-S(mm)) over the randomness of W (0) A, B, satisfies for every E
[L - 11. every i [nl, and every W with ||W w
S w for w E [0, 1].
Fi d
Fi
VV F 00
x 7
Vw R S
x m
(4)
d
The full proof relegated to Appendix
D.1
Here we give an outline.
Proof Outine. The argument is based on the bounded forward/backward process at W and the crokappppaattonn formula. For each E [n] and I E [T. 1], i.e., the residual layers, we have
(V,,F((Will +
D (Bhi, - vi)) h
5 F(W),
where the last inequality is due to that the forward/backward process is bounded for all the W such that IWW- 1 (Lemma in Appendix).
This gradient upper bound indicates that the gradient of residual layers could be much (r 1) smaller than the usual feedfoward layer.
3.3 CONVERSE RESULT FOR 1/D(VL)
We have built the stability of the forward/backward process for S 1/)(VT).. We next establish converse result showing that r is slightly larger than 1/S(VVL,, the network output norm grows uncontrollably as the depth L increases, which justifies the tightness of the value T = 1/2(vL)) for arbitrary I..
Theorem 4. For the ResNet defined and initialized as in Section 2 ifT L +te, then in expectation
E1 > L
Proof.
The proof is relegated the supplemental material in Appendix G
This indicates the value of r = 1/5)(VL) is tight for characterizing the forward stability of learning ResNet. We note that the theoretical results Section hold for very mild condition i.e., high probabiltiy is obtained when m > (llog(nL).. In the next section, we will show that gradient descent guaranteed to find the global minima for training ResNet if the network is properly over-parameterized when I 1/S(V/T..
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/ban bawwaddbbckwward stability. One first guide is that ResNet can be effectively trained even without normalization layer if choosing 1/VL, L, as shown in the experiments in Section
Our experiments demonstrate that the training performance of ResNet with 7 is on par with the ResNet with BN for all depths {20, 32, 56, 110, 1202} on CIFAR10 classification task. The test performance is bit complicated: ResNets with J drop 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.
5

---

Under review as a conference paper at ICLR 2020
2019ah; for depth 1202, ResNet with is slightly better than ResNet with BN. This motivates to study the potential benefit of combining BN and т.
We observe that although the residual block output exponentially, it still increases as traversing through layers. We give an hcuristic estimation on how the residual block output norm grows for ResNet with BN. Take the image classification task as example, the input is normalized across channel and batch. Therefore, for (gt) = BN (h:-)) We further assume the
of ResNet with BN does not increase
0, 1, ,,., L independence of each (ğt) ). Then, we have the following estimation.
we assume that Var (ar(()))) [[)) 1 for all I,... m and I
Claim 1. The output for ResNet with BN grows with E 12 =2 nmL, where 11 [hL1, hLa]-
The calculation can be adapted from the proof of Theorem
4 This indicates that the output norm of ResNet with BN grows roughly the rate VL. We propose that adding 1/vL on top of BN can keep the output norm roughly constant across layers, which produces considerable performance gain especially for deep ResNet.
GRADIENT DESCENT CONVERGES TO GL.OBL MINIMA FOR LEARNING OVER- PARAMETERIZED RESNET
In this section, we establish that gradient descent can converge to global minima for learning over- parameterized ResNet with т S 1/S((VT.) Compared to the recent work (Allen-Zhu et 2018b), result enlarges the region of that admits the global convergence of gradient descent. Moreover, our result also thcoretically justifies the advantage of ResNet over vanilla feedforward network in terms of facilitating the convergence of gradient descent. Before stating the theorem, introduce common assumption on the training data (Allen-Zhi et al.) 2018b Zou and Gu 2019 Soltanolkotabi 2019).
Oymak and
Assumption (training data). For any Is, holds that ||=>||| = and (zi), = 1/v2. For every pair i [nl] assume ||.. 2z 8.
We further assume that the loss function E(., -) is quadratic and the objective function for individual sample becomes F2 F((W): == 1 Bl,,, - 11
Theorem 5. Suppose that the ResNet is defined as in Section with T < L/S((VLlo m) and training data satisfy Assumption / If the network width m 2 Qn 1,55" m). then with
probability at least 1 exp(- (llog m)), gradient descent with learning rate 1j O ( )inds
point F(W)= < E in T 2(n28-1 log n log m iterations.
Proof. The proof is deferred to Appendix
This theorem establishes the linear convergence of gradient descent for learning ResNet with 5 S 1/D(vL log m). Compared with Allen-Zhu al. (2018b); Du al. 2018)) our result significantly enlarges the range of r (from - S 1/ m) to S 1/Ω(v T. log m)) that can guarantee the global convergence of training over-parameterized ResNet.
Moreover, we argue that even for r 1/92(VLoo m), the depth dependence for learning over- parameterized 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. 20188). This theoretically justifies the advantage of ResNet over vanilla feedforward network 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 due to the limit of bounding techniques when handling nonsmooth activation. Better bounding technique smooth activation function may help remove such dependence. We leave this for future study. For the case of r > 1/2(v (L), the global convergence cannot be guaranteed because of the instability of the forward process for extremely large depth shown in Section 3.3

---

Under review as a conference paper at ICLR 2020
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.c., 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 ffforard/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 semi- smoothness 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 w 1 and TZ L S 1. With high probability,
have for every W E (Rmxx)4 with [|Wr, L w ll2 S w and [| - 1000 1|2 S Tw for I [L- 1].
and for every W E (Rmxm)) with W S w and WWlll S for 1 E [I. 11, we have
I| +0 (VmnLu")) (TI)
F(W
SF(W) (VF(W), W +
nm
|
In 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 first-order term (the last term on the right hand side). One can see that as m becomes large in the over paramtteriaaatioon regime the effect of the first-order term becomes small comparing to the second-order term. Interestingly. if one replaces W', and W with the gradient upper bounds in Theorem 3 only the first-order term depends on I. while the second-order term, which dominant when m.. is large, is dlepth-nndependent 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).
EMPIRICAL STUDY
In this section, we present some experiments to verify our theory. We first demonstrate that 7 1/VLL is a sharp value in determining the trainability of deep ResNet. We then show that practical ResNet with 7 be efficiently trained even without normalization layer. We finally show for ResNet with normalization, that adding r also achieve considerable performance gain for both CIFAR and ImageNet tasks.
5.1 THRORETICAL 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 the ResNet model except the skip connection (see Section (). The models are generated with width m = 128 and depth L E (3, 10, 30, 100, 500, 1000} and We conduct experiments with T = 7. 7 Tu and show how affects the training performance. We use MNIST dataset (LeCun et al. 1998) and do the classification task. We train the model with SGD and the size of minibatch is 256. The learning rate Ir is set as I = 0.001 without heavily tuning.
Experiment results. We plot the training curves of feedforward network and ResNet with varying depths and widths in Figure We see that both r 1 and = 1
L.S are able to train very deep ResNets successfully. However, when Io. . the training loss explodes for models with depth 30
L
"The smoothness is compromised from the usual sense hecause of the non-smoothness of ReL.U. *GD exhihits the same phenomenon. We SGD due the expensive per-iteration cost of GD.
7

---

Under review as a conference paper at ICLR 2020
and more. This indicates that the bound т vz. is sharp for learning ResNet with arbitrary depth. Moreover the convergence of ResNets with r 7. and f,o.s 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.
depth.10
digit 22
s4pth.00
0e11)
oven
expt 1
1etth
0e10116 10
0k:0.20
1000
302 dight 1000
0k2h: 306
06:
disth.000 3000
02
training
training
training steps
training
Figure I: Training curves for feedforward network and ResNets with T = t. Z left to right).
and
Zarz (from
5.2 LEARN RESNET WITH
We use more experiments to demonstrate that ResNet can be trained efficiently with r even when there is not normalization layer.
In this section we conduct experiments on CIFAR 10/100 datasets. We use the ResNet models (He 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 learnable parameter with initialization 1 1/VL. Following Zhang et al. (019a), the learning rate of scalar parameters is divided by 10. All blocks share the same and we use the averaged gradient to update v. Figure 2 shows the training/validation curves.
CIFAR10
CIFAR1O
CIFAR100
CIFAR100
1.50
3.0
$ 1.25
2.5
1202
0000
deph__0
depta_20
2075
dephh 32
dapts 22
depm 56
degt 56
depih 110
110
0.25
d202
0.5
d222
0.00
50
100
1.50
100 Easih
150
250
100
150
230
100 Esoch
150
250
Epoch
Eaoch
Figure 2: Experiment results on CIFARIO/100 with 7 initialized as VI. All normalization layers are removed.
With r initialized as VT. 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 From Table 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 out runs for training ResNetl 1 202 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 7 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 7 and the Fixup scheme Zhang et al. (2019a). Transformer 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
8

---

Under review as a conference paper at ICLR 2020
Dataset
Depth
ResNet FixupInit
ResNet +
20
8.72(+:0.6)
8.39(=0.11)
32
7.99(#0.22)
7.68(=0.10)
CIFAR 10
56
7.45(+:0.37)
7.07(::0.16
110
7.24(+:.122)
6.52(=00200)
1202
7.83(+0.18)
6.08(=0.21)
Table I: Topl validation error CIFARIO. Numbers average of runs except ResNet + Fixup (standard deviations are given inside the bracket).
Epoch-50
Epoch-
18
18-
ResMet1202-
1n
14
ResNee1222--
ResNet1202
14-
Ros2Me11002+
nor raiio
RenNel1202-1
8-
50
100
150
200
50
100
150
200
0
50
100
150
200
number blockes
number blocks
number of blacks
Figure 3: Output norm of ResNetl 202 over layers at different epochs. X axis is the index of block. Y axis the output norm ratio compared to the first block.
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
top of normalization achieve even better performance.
We first illustrate how the output norm of each residual block grows for ResNet1 with BN (He et al. 2016 loffe and Szegedy, 2015) in Figure We see that epoch 0 (initialization stage), the output norm grows almost at the rate vi as estimate in Claim After training, the estimation in Claim is not as accurate as the initialization because the independence assumption does not hold after training. Nonetheless, by adding across the forward layers and across the training epochs.
top of BN, the output norm keeps roughly constant
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 modification is multiplying a fixed - 1 at the output of each residual block (right before the residual addition). For R 202, we do not small learning rate warm up the training. The validation errors on CIFAR 10/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 ResNetl 202 on CIFAR 10 worse than ResNetl 10 as shown in He et al. (2016). As grow and imbalance
the same in He al. (2016). The only
VL
depth increases, the the benefit of adding layers. As shown in Figure 4 ResNets+BBN+r +7 keep the output norm roughly constant and make good use of the network depth.
layers hurts the performance, which covers up
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 _ 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 in He al. (2016).
Table shows the results on ImageNet. We can see that by just adding a T on top of BN we can achieve considerable performance gain. We note that trick in Goyal al. (2017) that initializes the scaling factor y of the last BN of each residual block to 0, shares the same spint as a small here, but does not have principled justification.

---

Under review as a conference paper at ICLR 2020
ResNet+BN R +BN+
30-
Val dation error
val dation arror
20
10
2
Net-NetBB
Res Nct-BN+1
110
depth
depth
Figure 4: Top1 validation CIFAR 100 dataset. The benefit of becomes larger as network goes deeper.
Model
Method
Validation Error (Topl)
+BN
23.6
ResNer50
+BN+T
23.0
+BN
22.0
ResNer101
+BN+T
21.4
+BN
21.7
ResNet152
+BN+T
20.9
Table Validation error on ImageNet dataset.
CONCLUSION
In this paper, we provide non-asymptotic analysis on the forward/backward stability for ResNet, which unveils that r - I/vL is sharp value in terms of characterizing the stability. Furthermore, when the network is properly over- pereparrmettrized, we show that gradient descent finds global minima for training ResNet with - < 1/9[VVL log m) which greatly improves over previous work of S L/ m). We also bridge theoretical understanding and practical guide of ResNet structure. We empirically verify the efficacy of the suggestion normalization. One interesting future direction is to bypass the semi-smooth argument and give sharp dependence on the depth and the number of training samples.
1/vL. for ResNet with/without batch
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet Iearn efficiently, going beyond kemels? In Advances Neural Information Processing Systems (NeurIPS), 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization overparamettrrized neural networks, going beyond two layers. arXiv preprint arXiv:1811.0491 2018a.
Zoyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via pvrrpaaraatttiiization. arXiv preprint arXiv: /8/ .00962, 2018b.
Zeyuan Allen-Zhu. Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems (NeurIPS), 2019a.
Sanjeev Arora, Simon S Du Wei Hu, Zhiyuan Li. and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: 008584, 2019b.
Devansh Arpit, Victor Campos, and Yoshua Bengio. How initialize your network? robust initialization for weightnorm resnets. In Advances in Neural Information Processing Systems (NeurlPS), 2019.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalcy-Shwartz. Sgd learns wer-paaaaeeterized networks that provably generalize on linearly separable data. arXiv preprint arXiv: 10174, 2017.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over pverpparamttrrize deep relu networks. arXiv preprint arXivv
2019.
Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over-paramen over-parameterized models using optimal transport. In Advances in Neural Information Processing Systems 31. 2018.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in diffcrentiable programming. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, arXiv preprint arXiv: 2018.
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 1.03804, 2018
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference Learning Representations, 2019.
Behrooz Ghorbani, Song Mei, Thendor Misiakiewiez, and Andrea Montanari. Limitations of lazy training of two-layers neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint 1rXivv1706.000 02677, 2017.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), pages 448-456, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in
neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statisticx, pages 1302-1338, 2000.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFF, 86(1) ( 1):2788-2324, 1998.

---

Under review as a conference paper at ICLR 2020
Yuanzhi Li and Yingyu Liang. Learning overparamettrrized neural networks via stochastic gradient descent structured data, In Advances Neural Information Processing Systems, pages 8168 8177, 2018
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli. Yann LeCun, and Nathan Srebro. The role of over- parametrization in generalization of neural networks. International Conference on Learning Representa- tions, 2019.
Emin Orhan and Xaq Pitkow. Skip connections eliminate singularities. In International Conference on Learning Representations (ICLR), 2018.
Samet Oymak and Mahdi Soltanolkotabi, Overparameterizee nonlinear learning: Gradient descent takes shortest path? In International Conference on Machine Learning (ICML), 2019.
Daniel Spielman and Shang-Hur -ua Teng. Smoothed analysis algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3)385 463, 2004.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, 2017.
Andreas Veit, Michael Wilber, and Serge Belongie. Residual networks behave like ensembles relatively shallow networks. In Advances in Neural Information Processing Systems (NIPS), pages 550-558, 2016.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. Compressed Sensing, Theory and Applications, pages 210 268, 2012.
Gilad Yehudai and Ohad Shamir. the power and limitations random features for understanding neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. In International Conference on Learning Representations (ICLR), 2019a.
Huishuai Zhang, Wei Chen, and Tie- Yan Liu. the local hessian in back-propagation. Advances Neural Information Processing Systems (NeurIPS), pages 6521-6531, 2018.
Jingfeng Zhang, Bo Han, I Laura Wynter, Kian Hsiang Low, and Mohan Kankanhalli. Towards robust resnet: small step but a giant leap. In International Joint Conferences on Artificial Intelligence (IJCAI), 2019b.
Difan Zou and Quanquan Gu. An improved analysis of training wer-parameterized deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- parameterized deep relu networks. arXiv preprint arXiv: 1.1188888, 2018.
12

---

Under review as a conference paper at ICLR 2020
A
USEFUL LEMMAS
First we list several useful bounds on Gaussian distribution. Lemma 1. Suppose X (O0 )²), then
x²
X[ S <x) 2
exp
2
xx X| S x $ V
Another bound is on the spectral norm of random matrix Veesshynin 2012 Corollary 5.35). Lemma 2. Let A R2 and entries of are independent standard Gaussian random variables. Then for every 2 0, with probability at least 1 (ap(--t/2) one has
Smax (A) S VN Vv++,
(8)
where Smax (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 T.
Theorem 1. Suppose that W A are randomly generated as in the initialization step, and Do...., Di are diagonal matrices such that [|Dill2 S 1 for all 1 E [L] and Dj is deterministic given (W(") a < 1}. I S (S(VV,,, then there exists some small constant such that with probability at least 1,2 -.2_exp( exp(- (M(mm))) over the initialization randomness we have for any >> a,
Do (I (I++W!") D6-1...... Da (.......((+TTT (T++W.0)) S 11+c
Proof. We first show for any vector ha-1 with | = 1, we have li S 1 + e with high probability, where
hbg D& + T (0) Do-1 D. W (0)
ha-1.
Using notations = 11-1 + -Wih-- introduced in Section the following
2 we have ||
2 |1el]]. Thus we have
|/
|
1196 12
119a 12
h 112 5
haa 112
| 1
Pha-1
1/6 1|2
Pa-
Taking logarithm both side, we have
| 1|
log 1/ 12
Σ log A
where A
(10)
|
If let h--1 = h--1 then we obtain that
log A: log (1 + 27 (hu-1, w/ h1 + ( 11)))
$ 2r (hu-1, 100h h1-1) |w hu
where the inequality is due to the fact log(1 + x) I x for all x -1. Let & =
2r [hr-1, w and G ? 112 then given h-1 we have N (o, 8r2)
& 2r2 x
We see that
log A 20 Σ
6
SP
$ Σ
b
e
+P
ΣS
Σ 1=a
b
e) 2
(II)
2
1=0
1=0
13

---

Under review as a conference paper at ICLR 2020
Next bound terms the right hand side one by one. For the first term we have
6
Ac 2
Ae
]
P
E
= P
exp
Σ
E1
2
exp
S E
exp
5 &
(12)
2
2
i=a
1=a
where À is any positive number and the last inequality uses the Markov's inequality. Moreover,
E
exp
A
E
exp
A
Σ
&
E
lexp (AE+))
Fo-1
2
6-1
= cxp
E
exp
A > E1
(13)
m
1=a
87 27 (b
+))
exp
Hence we obtain
mc²
mc² (14)
P
Σ 1=a
E
S exp
(1288 (b- a a
= exp (-9) >2 - (((b-a1))
2
by choosing À =
mc
and < 1/S(vL). Due to the symmetry of Σi=a Et, the conclusion can be
32
generalized to the quantity Σi= Erl-
Then, for the second term, we first present a concentration inequality for the general X2. distribution X (Laurent and Massart 2000 Lemma 1)
PP (|X ml
(15)
Then for Σ/ Liza St by applying the above concentration inequality and Jensen's 's inequality, we have
Fo-1 )
P
=
E
P
2
2
1=0
1=a
b-
2r - +1) )
<
E
P
G6 Σ
Gi 2b a 1++++1
2 2
I=a
b-1
P
166 2T
2
(4L - 2)7²
Σ
Sk Fo-1
2
k=a
b-1
(Fa-..) 1
E
P
m
Sh
>
m
(AL - -2)22
Σ So
27
27
2
k=a
b-1
E
exp
m
(4L 2)7
Σ
CK
1674
k=a
E
exp
+
1674
4
mc²
exp
(-2
(16)
Combining equation 16 equation and the condition T S ((VT)) we obtain ||Aa|| S + c with
1
probability at least 1- exp(pppppSS 22( me 74g )), where we use approximation log(1 + c) is c for small c
to simplify the expression. Taking e-net over all m-dimensiioal vectors of ha-1. with probability 1 1-
the inequality 2 holdd for fixed a and b with 1 < a < b < L. Taking a union bound over and b, the conclusion proved.
14

---

Under review as a conference paper at ICLR 2020
The e-net argument is as follows. We have proved for given unit vector ha-1, || + with probability at most exp(-S2( me )) for small constant c. Let Nr be an e-net over the unit ball in In' with 1/11, then we have the cardinality [We] (1 +1+ 2/e)"" < (23) Taking the union
bound over all vectors ha-1 the net Ne. we obtain
mc² T
P
max ||4b|| > 1+ of Ea-
3 (1+ 2/e) exp
(-2
(-m
mc²
= exp (-m
Ω2
log 23
?
By choosing the coefficient of 7 appropriately, we can make 92
log and then the right
hand side can be written as exp (mm (-52( (-m((=+)) Based on the result /Vershynin 2012 5.3), we have
Lemma
D (I++w!!) Db-1 Do (I ( (1--))
max Ra-1EN
||blll2
1.1 max
We complete the e-net argument for the spectral norm bound by introducing a new constant c.
C BOUNDED FORWARD/BACKWARD PROCESS
C.I PROOF INITIALIZATION
Theorem Suppose T 1/D((VL), There exists some small constant e. such that with probability
at least 1 O(nL) e m(((mme)(ee over the randomness of A IR and W E (Rmxmme the following holds
vi [n], 10, L)
| E - +
(3)
Proof. We ignore the subscript (0) for simplicity. The upper bound of ||,, can easily achieved by the proof of Theorem Now, we give the lower bound of [/,, First we have
|| ||م,oo||
| |
[|a,,l| = |hhool|
(17)
Then we see
| ||
log ||h,,111
log ||h,o 1 +
log
1hiaa-1 1|
|
112
|1 1
log ||/4,,0 11
log 1+
(18)
hi.a-
2 log |/4,00 2 +
Σ (Aa
-22)-
where A, = | |
- and the last inequality uses the relation log(1 + x) 2 x - x2 We
give lower bound A.. Let be the set {k: k [mi] and (hi,--1) (W ahh,a-1)) 0).
15

---

Under review as a conference paper at ICLR 2020
We have that
m
Aa
(hs,a- 1)22 2T (Wohii-)) + (FWahia-Di
(h1,a-1)k
11/,a- 2
1/ 112
kES
Am
(1),a-1)2+
1
Σ
( 1))
2
Σ
T(hiaa-)) (W
allia-1)zz
| 11|
|
1|
| 111
RES
BES
2
T W kiia-1)2 +
(hia-1)x(W
(Waliaa-)
| 11
1 1
|| 1i1
2r (hi,a-1, W Wallia-1)
(19)
||
||
where the inequality is due to the fact that for & & S, 1(hia-1)al < (T
W a )al
and
(hi,0-1)& (W ahi,a-1) S We let Ea = 2r(ha W. aah and Sa = || -
then
A. Ea Sa. We note that given 11,a-1 Ea N 0, 8r and Ca 2r Xm- Due to equation 14
and equation T6 we have
mc²
P
E
S 2 exp
2
128 a +
Ima
(20)
(mc²)
)
P
1
2
exp
-
2
74
1=a
Then for any >> O, and r S
we have
D(VL)
P
A
= P
Σ
A
Σ
&a
+P
Σ
A S
Σ Ea
1==1
1
c)
< P
Σ
Sa
+P
Σ Ea S
- -((cmm) m)
2
2
(21)
We can derive a similar result that obtain that for single A..
Σl Aa 20) $ c R(((m)) Let a in equation
20 we
P(Aal 5e (((mmo?)
(22)
In addition, we that
Σ P A 2 /i) < 21e M -m)
P
Σ 2
c
2
(23)
a=1
a=1
Thus, similar to the equation 21
we obtain
I
Σ
A.
A -0)
< 2Le -2(-mmin((
(24)
a=1
which results in
IP (log ||, S -c)
SP log |1, 2 + (A. A3) S 5c
2L (mminfee?))) (25)
Then we get the conclusion.
16

---

Under review as a conference paper at ICLR 2020
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 1/ 6( + W
1 (/ and h4s o((1 TWi) for 1 E [L 1). and h o (W ( 11 and h4 (WLh,,L-1). Furthermore, (0) let h4,, := h4p1 hip and D D D ! Then the spectral norm bound after perturbation is follows.
Lemma 3. Suppose that W A are randomly generated as in the initialization step, and Do..... Dí, are diagonal matrices such that |D S for all I E [L] and DV is deterministic given (W(O) S 1}, and W Wi...., WL E Immx are perturbation matrices with || Will < Tw for all I [T. for some w 1. Then with probability least initialization randomness we have
(L) exp(-S((m) over the
[[I+ b + + ...
"I D + +TWllla s O(1)
(26)
Proof. This proof based on the result of Theorem T b < L
From Theorem
1
we know for any S a S
III - (0) Dz
D
+ (l
Then we have
[I(I + 7
+TW() D* D' -
b-a+1
1 (FIIW"II) (1+ (1 (1+ (1+ S 00(1 cc),
j
j=0
due to the assumption |illl S Tw for E [L - 1] and w L S 1/S(VD).
We also have small changes on the output vector of each layer after perturbation.
Lemma 4. Suppose for w < 01), 72 < 1, [W'l22 < w and || [Wlll S for E [L 11. Then with probability at least - exp(-S((mma ((m=-(((m))))), the following bounds on Ki, and D'., hold for all i E [r]] and all E [1]
[Kaall S O(F)Tw), [|D', s (m(wTT)(*)) || S O(w), [|D S (ocalo.smmmm00 (mm)
Proof. Fixing and ignoring the subscript in i, by Claim 8.2 in Allen-Zhu et al. (2018b), for I e [L 1], there exists D such that [(D)) ) I and
M= = D (I (I++W, + + Wi) - (I )W
= DV -
=
Σ
... D + + rW D'
(27)
We claim that
|| < 0(>²Lw)
(28)
due to the fact | < and the assumption || |Wlll S Tw for / E IL - 1]. This implies that [| [lu O(r Lw) for all [L-1] and for all with probability at least O(nL)-
exp(-Q(m)). One step further, we have [| |l || & O(w).
17

---

Under review as a conference paper at ICLR 2020
As for the sparsity |Diilo, have |Diilo ((m(wTL)))) for every = [L and |D 1
Om.
The argument is as follows (adapt from the Claim 5.3 in Allen-Zhu et al. (2018)).
We first study the case for / [L 11. We observe that if (Di)ss + 0 one must have
(g))sl > K(9 )gl
We note that (of )) = (//_1 + rW, (0) (0)
1annnnnn h(=1) ~ N (((((1)))))
(0) 1113 Let & 1 2/m be
parameter be chosen later. Let S1 S [m]] be a index set satisfying S₁ == {i Kg ), s {T}. We have P((() (0))
)g( < {T) S m for each j E [m]] By Chernoff bound, with probability at least
1 exp( (2(mm((m))2) we have
S s O(5m3/2).
Let S2 = -i: j $ S1, and (Diss # 0}. Then for j E S2, we have (g)) > ęT. As we have proved that ||+||| S 0 Lw), we have
10112 (ET)²
SSa
((WTL))//E))
Choosing & to minimize |Si] + [S2). we have & = (WT (WTT.) //mm and consequently, | ((m(wT))))) Similarly, we have | lo O(mwffa).
<
We next prove that the norm of a sparse vector after the ResNet mapping.
Lemma 5. If s 2 Q(d/ log m) and T S. 1/S2(V)), then for all i E [n] and E [L] and for all s-sparse vectors u E R and for all IRd, the following bound holds with probability at least 1 1- (nL) + exp(-S((s l))
Vslog m -WW------------------- Ds,o + WW. wu
(29)
Vd.
where Di,a is diagonal matrix with value and it independent of W b for any b (a, LJ.
Proof. For any fixed vector E Tm I W D + + DiaaII WWa <
1.1 u|l holds with probability least 1 exp(-(2(m)) (over the randomness of W,, [L].
On the above event, for fixed vector v E Rd and any fixed W, for I E [L]. the randomness only comes from B, then x BD,,,. W, W.D.,.110
(.-1)... -,, -W .)u Gaussian
variable with mean and variance no larger than O([]u]| [[ol//Vd). Hence
P( BD.,, W D. ( -
Di.a + JWlu 2 / Vslogm [(Iul]][e|//ad)
errc(S((V logmm) m)) exp(- log m)).
Take c-net over all s-sparse vectors of u and all d-dimensional vectors of v. if 2 22dd/ log m) then with probability exp(-((s log m)) the claim holds for all s-sparse vectors of and all
d-dimensional vectors of v. Further taking the union bound over all i E [M] and a E [L]. the lemma is
proved.
D GRADIENT LOWER/UPPER BOUNDS AND THEIR PROOFS
Because the gradient is pathological and dete-depen,nnt, in order to build bound the gradient, 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 union bound.
18

---

Under review as a conference paper at ICLR 2020
We define the BP w intermediate output h or the parameter W at the specific layer using the forward propagation state of input / through the network with parameter W. Specifically,
W.,
(v,,) operator. It back- poock-ppppggtess vector to the which could be the
BP w. (1, b4) (I + W Di141 ... .. 7 D., D...B'' BP W. (c, W1) : (Di,( + +TW411) ... ( (G
1 W [L--]]] 1},
BP (c. WL) = (DILB'') hi.L-1
Moreover, we introduce
BP 7, Wi) = Σ BP w. (1, Wi) vi [c].
where & is composed of vectors V, for i [n]. If 0 is the error signal of input i, then
Vw, F.(W) = BP w. ( (Bha, - Vi Wt).
D.I GRADIENT UPPER BOUND
Theorem 3. With probability at least 1 (nL) exp(- the randomness of (()) A, B,
satisfies for every E [T. - 11, every i [n], and every W with | - w100 S w for w E [0, 1].
Vw. F. 00 ( (Fi(W) (F(WW)
(i((W)
x 7²2m)
Vw, F, |1 0o
x m (4)
d
d
Proof. For each E [n]. we have
BP W (4. W 2) Di. (BTrz) -r-1-111 = Di, (B'rz) || s S((mm/d)
Similarly, we have for 1 E [L 11.
BP W (vi Wolls = Di.i( + (...:.....(.................... D' h
/O(TVm//dlll:)
The above upper bounds hold for the initialization W because of Lemma and Lemma also hold for all the W such that || W la S w due to Lemma 4 and Lemma
They
Finally, taking net over possible vectors & (U1, ......., vn) bounds holds for all J. In particular, we can now plug in the choice of u; Bla, yf and obtain the desired bounds on the true gradients.
E (Id'),, we prove that the above
D.2 GRADIENT LOWER BOUND
Theorem 7. Let w = O 63/2
With probability at least - exp( exp(-Q(mw?(1) over the randomness of (w),, A, B, satisfies for every W with W
log"
W (0)1 S w.
F F(W dn/ō
VV F(W) 1
Ω
x m
(30)
This gradient lower bound on V Ww, F F(W)
I acts like the gradient dominance condition Zou and Gu 2019 Allen-Zhu et al. 2018b) except that our range w does not depend on the depth L..
Proof. The gradient bower-bound at the initialization 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
19

---

Under review as a conference paper at ICLR 2020
high probability the gradient is lower-bounded. although the worst case it might be O. We adopt the same proof for (Zou and Gu 2019 Lemma 4.1) based on two preconditioned results Theorem and Lemma 6 We shall not repeat it here.
Now suppose that we have || V WWWFFWW ((WW)) 2 Ω the gradient after perturbing the parameter. Recall that
F(W dn/8
We next bound the change of m).
0 BP O ( W r.) - -PP w P W 1)) Σ (D
(v) BD,,,. (1a,)-))"))
By Lemma and Lemma 5 we know,
| BD of BDi, & O(V 50Vmmw* mwf/s Vd) ||v||]-
Furthermore, we know
o BD S Olv m/dm ||evll.
By Theorem 2 and Lemma 4 we have
S 1.01 and || - 11 11- S 50(w).
Combing the above bounds together, we have
|BPP w S W..) - BP w 7 W S ~n|l O(y musii / m
+ w m/d)² s /n n| o (m
Hence the gradient lower bound still holds for W given w O
6//2
Finally, taking e-net over all possible vectors रे = (U.,..., 2n E )n we prove that the above gradient lower bound holds for all 7. In particular, we can now plug in the choice of e; Bhh D 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 xz) sattisfying ||x, 12l 2 then ||h,, h₂rll 2 26))) holds for all | [L] with probability at least 1- Lexp m)) for S 11S0///1/ log m) and 2 228-1228-2
The proof of Lemma 6 follows that of (Allen-Zhu et al. 2018b Appendix C.I) given the condition that 2 12721128-2)
E SEMI-SMOOTHNESS FOR T < 1/Ω(vV)
With the help of Theorem 3 and several improvements, obtain tighter bound the semi- smoothness condition of the objective function.
s2 (((m
3/2
Theorem 8. Let
0(1) and W (0), A, B be at random initialization and
log
P < With probability at least 1 exp( (1mm over the randomness of W (0) A,B, we have for every W E (Rmxm)& with W w 112 S w and WW - ( || S Tw for I [T-- 1). and for every W (Rmxm)) with W L1ll S and Will S for [L 1]. we have
F(W + W ( + (VF(W). W O mm
d
+0
mnLw"/
(TL)
(31)
d
Before going the proof of the theorem, introduce lemma.
20

---

Under review as a conference paper at ICLR 2020
Lemma 7. There exist diagonal matrices D e R=x" with entries in [-1,1] such that Vi [l [L 11.
1ag hu11 +'J(+++WW+))) (. +I+ rW (at)) + D hi (32)
and
hi
T1g =(Di, D',,
L-1 D(D'+DD'WWW ... (I aWa+))D + D",.)TWahho-r (33)
a=1
Furthermore, we then have VI E [ - 1/a halll & Ow7² D S O(m(wTL))1)) and [|N._ ha,ell S ((1 Tv (' [[e), ||D s (m/ and
Bh - Bi. S O(v ml/m//)/W'l/>>
hold with probability 1 - exp(- exp(=X((mm"))))) given ( S Wilk S Tw for 1 E [L 1] and S TVL,
Proof. The proof adapt from the proof of Claim 8.2 in Allen-Zhu et al. 2018b) and the proof of Lemma 4
Proof of Theorem g First of all, we know that loss; == BB vi
1
Bh
1/
2 |loss: + B(hi, - hr.L)l12
2
2 |oossll 2 + +loss; B(hi,L - hr,2) + B(h - hn,1)11
(34)
and
F(WF(W)= Σ (loss BD ... + +W.)) (rhaa-1)
(35)
Vw, F() = Σ (loss BD&,)) "BD.,)((h...)))) (ha.-1)".
(36)
Then,
F(W W F(W) (VF(W), W
= =-(VF(W), W + Σ Bhis vEl1 |Bh vi11
loss: B(hEL ha, + 1 B B(tt. -
Vw. F(W, Wi) +
(a)
loss: B (IDr, ((DI,,+D'',.)) B(U,L h, Σ
T
loss; B ((D.. D (.+.).............. (W+ Di
T
D. W + D.
(37)
where (a) is due to Lemma
21

---

Under review as a conference paper at ICLR 2020
We next bound the RHS of equation 37
We first use Lemma to get
[b ha,1)l O(v OmVm/d)
(38)
Next we calculate that for 1 = L,
|loss;
T B (Di,, + - -D. (..........)))
$ loss; B (D",, W (Wb.,-11)
+ loss; B (D W', (hi,e,-- -1..--1-hh--1))
(39)
For the first term, by Lemma and Lemma
we have
mmw
T loss; W W WhiL--)) 5o
||oss:|| || h
vd
Vmw
0
|[ooss:|] ||
[|WLlla
(40)
Vd
where the last inequality is due to | 0()) For the second term, by Lemma 7 we have
loss: B
T
(Di. ( -hac-i)
$ ||oss:|||
[DD.L (W'llallba,a-1
ha,L-all
(w/mm 1.'..l2.
- |loss:||
-
(41)
Vd
where the last inequality is due to the assumption [W s w. Similarly for / E [L - 1]. we ignore the index for simplicity.
T loss
... (BDD++ D BD (I +I++WWa. (Wi+1)D Wi(
loss (D
(D: - (D.+
loss ...
Σ
loss T
WD W. (I
W hn-1)
(42)
We next bound the terms in equation 42 one by one. For the first term, by Lemma 5nd Lemma
7
we have
T loss (D
V %/
loss
Σ 1=1
Wt
(D: (T
Vd
(a)
Vmw"%s
0
||oos|||
(43)
Vd
where (a) is due to the similar argument in the proof Lemma and the fact W
WD +I
D = O(1) and ||/ = O(1) holds with
high probability.
22

---

Under review as a conference paper at ICLR 2020
We have similar bound for the second term of equation 42
1-11-
Loss BD (1+ TW
- -DD (+
Vm(WTTb L)
L-1 Vall
0
||loss||
/all Wailf
vd
a=1
vm(wTL)p L)9/
0
||oss||| TL
W L-1:lle-
(44)
Vd
For the last term in equation
we have
loss BD ... (I+ (i h1-1)
$ |loss||| o (vm/d)) W - LW
||oss|||
O O (Vmmd)
W (722)
(45)
where is the last inequality is due to the bound on | - -h-hil in Lemma
Hence
Vm(WTL)8%
equation 12 <O 0
||loss|| 3/3 W L-talle
Vd
VmLw%/ -|loss||
00
(TL)%
|| 1-
(46)
Vd
Having all the above together and using triangle inequality, we have the result.
Proposition (Proposition 8.3 in in Ailen-ZZhu et al. (2018b)). Given vectors a. E R and Ia,20- Then, there exists a diagonal matrix
D E R mm the diagonal matrix where DE.K
D" E pmxm with
Da.k + D S and Di S for every k E [m].
D + 0 only when 1a,20 F 16.20
b(a) - ((b) = (D D")aaa(--b
Proof of Lemma Fixing index and ignoring the subscript in for simplicity, by Proposition for each / E LL 1] there exists D such that ((D"),, < and
h1 - = = + - WW W - ((
= -Di+ + (D'+ (
-D, ++)) +D. D
ED. - a+)) + DD) W'ah--
Then we have following properties. For I E [L 1), ||4 - hull S Ow?)Iw).
Iw). This is because
[[ + (I -W,) ... (I + -W a+ [D, + Dz)! 1.1 from Lemma | s 0(1)
from Theorem and the assumption [ & Tw for I -1.
23

---

Under review as a conference paper at ICLR 2020
To have tighter bound on liا - he let introduce W == Ee=s(Di D (I+ W (D, + D") W", for 1,..... I. Then we have
hr - hy = [W WT Will
7 11: 1-2 Tho
(47)
It is easy to get
||[T// The
T 1 1
72
ha
1 S STV. 0(1),
e=0
where the inequality is because of h S (1) from Theorem 2
Next, we have
[W", WT
Wl]ll2 [W". W W
Σ (WT)) IB 1. 1.1,
Σ (W)) L.1l (48)
where the second inequality is from the definition of spectral norm, the third incquality is because of [I + DI) + -W,) (I+ rW (D+ + +D"Il I 1.1 from Lemma
Hence we have lik hell so - ((L
O [ ||x) because of the assumption
TVISL.
For I [Z], Ilo < ((m This is because (D k. is non-zero only coordinates & where (0)) and (9)) have opposite signs, where it holds either (D
(0) )a, + (Di) or (D()) ka.k + (Di)a.k. Therefore by Lemma we have || llo O(m(wTL)))) if [|Will2 2 S TW.
F PROOF FOR THEOREM 5
Theorem 5. Suppose that the ResNet is defined as in Section with t S 1/52(
(/S2(V/..o) V......oogg m) and training data satisfy Assumption ! If the network width m 2 Q(n L38-Adlog" m), then with probability at least exp(-S2(lop m)), gradient descent with learning rate rj O d finds
point F(W) < in T = 22n28-1 log a log m iterations.
F.1 CONVERGENCE RESULT FOR GD
Proof. Using Theorem 2 we have ||A la S 1.1 and then using the randomness of B, is easy to
show that Bh (0) yi 2 s Ollog m) with probability least wexppx(((()))))e m)). and therefore
F w())) I On log" m).
(49)
Assume that for every t = 0, o....... T 1, the following holds,
53/2
(w( " ww =
(50)
W w 1 S
(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 indeed satisfied.
Letting V. VF(W we calculate that
F F(W(++1) < F(W nl V
m /.)l
7V F(W
(r1.)//)
d
(10m) dn
F(WiC)))
(52)
24

---

Under review as a conference paper at ICLR 2020
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
7 O(d/ (mn)) and the assumption
equation 50 That is, after T 52
da log
lolog" i
mpom
iterations (TW(T) c.
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[[) L. w l2 S Olv add m
To guarantee the iterates fall into the region given by w equation 50 we obtain bound m n 8 "dL" "og" m.
G TIGHTNESS OF T = 1/VL AND THE PROOF OF THEOREM 4
Theorem For the ResNet defined and initialized as in Section 2 if
L 2 to. then in expectation
E/1 L
(5)
Proof. By induction we can show for any &o E [m] and I E [T.-1] 1],
Σ (rW oha-)) a=1
(hr)a 2 Φ
(53)
is easy to verify (h1)s = - < ((ho) + mhoa) 2 o ((TW2hoa)) because of (ho)) 2 0.
Then assume (hi)s 2 o (Ei=r (TW aa we show it holds for + 1.
(h(41)x = d (TW:+14u))) 2 ( ( ) + (r (iWa)hh)a) 2
[+1
Σ
(T (TW dla-
where the last inequality can be shown by case study.
Next we can compute the mean and variance of E'_1 (r (aWhha- 1)2 by taking iterative conditioning. We have
2
E
(TW 11 = O,
Σ (rW (Waha-i)2
(54)
m
Moreover, (7 (TW h/a-1)k are jointly Gaussian for all a with mean 0 because W. are drawn from independent Gaussian distributions. We use [ - 2 as an example to illustrate the conclusion, it can generalized to other 1. Assume that hg fixed. First it is easy to verify that (r (eWWhh) hho) is Gaussian variable with mean 0 and (7 W2h1)s Wi is also Gaussian variable with mean O. Hence [(TW (ho)s, (2))) follows jointly Gaussian with mean vector [0, 0). Thus (r WWWhha (rW, 2h1)a )a Gaussian with mean O. By induction, we have E'_ ( (TW Wahah- cha--)k is Gaussian with mean 0. Then we have
E h1
Σ
E
Σ
(TW (iaalo--i))
- k=
E Σ
(TW (rWahoon (rWaha-1)s)
1=1
a=1
a==l
m
2 2a=
E
E hla 112
(55)
m
where the first step due to equation 53 the second step is due the symmetry of Gaussian distribution and the third step is due to equation 54 Since (hı)x o ((hz-1)& + (Wiht-1)x) we can show (hh) > (h,-1) given h1-1 by numerical integral Gaussian variable over an interval. Hence we have 1 2 E1 ...2 E Eholl by iteratively taking conditional
25

---

Under review as a conference paper at ICLR 2020
2.4
2.4
2.2
depth_1000 1000
2.2
depth_1000 1000
depth_5000 5000
septh_5000
training 109
8
1.8
depth_10000
1.8
depth_10000
144
144
train graining
1.0
1.0
0.8
0.6
0.6
0.2
0.2
0.0
0.0
5000
10000
15000 20000 25000
5000
15000 20000 25000 training steps
10000
training steps
Figure 5: ResNet with 1000/5000/10000 layers. The width 8 for the left figure and 16 for the right.
expectation. Then combined with equation 55 and the choice of 7 - we have Ellht-1lf _ Because of the random Gaussian initialization of WL and hy = =(W Lh2-1), we have E |ll | Thus, the claim is proved.
H MORE EMPIRICAL STUDIES
Dataset
Model
BLEU
Transformer Vaswani al. 2017)
34.8
IWSLT DE-EN
Fixup Zhang et al. (2019a)
35,0
Transtormer
35.6
Transformer Vaswani et al.
2017)
28.4
WMT EN-DE
Fixup (Zhang et al. a2019a)
28.1
Transtormer
29.1
Table 3: Experiment results on machine translation task (Higher is better).
In this section, 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 fixed right after each residual addition and removing all the normalization layers. We do not use scalar bias our Transformer-+r model. For IWSLT DE-EN, we adopt the Transformer-har model and set 7 0.5. For WMT EN-DE, use Transformer-br model and set T = 0.3. Dropout is set as 0.5 for base model. For big model, we set attention dropout and activation dropout 0.1. Other hyperparameters are the same as Vaswani implementation by Zhang et al. (2019a). All models are trained for 150 epochs with 25k batch size. We average the checkpoints the last 10 epochs and evaluate the BLEUU score. The scores are shown in Table
(2017). For Fixup, we the
I EXTREME DEEP RESNET
Per reviewer's ss request, we plot the training curves of extremely deep ResNets with the width m {8, 16} and the depth (1000, 5000, 10000) in Figure We set = z 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.
26


Reviews:
[{"review_id": "rylD2kolqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis is an interesting submission which presents important theoretical results while also showing their practical pertinence via experimental validation. \n\nThe 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. \n\nThe 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.\n\nThe 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. \n\nMinor comments:\n\"What else values\" ---> Are there other values \n\"our first claim is a new spectral norm\" -->  is a new bound of the spectral norm\n\"we does no make such\" --> we do not make\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ryePM53AFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors analyze the stability of a randomly initialized ResNet in terms of the scaling of the network and its depth. They claim to characterize the spectral stability of a randomly initialized network (and local perturbations of it), as well as that of the forward and backward process. These results, along with some further results, are used to extend convergence proofs of ResNets towards more standard initializations. Some of the claims are evaluated empirically.\n\nUnfortunately, this paper is not a good contribution at the moment, as the work, although potentially interesting, is somewhat incremental and poorly presented. In particular, the results (including the proofs) only extend the results from Allen-Zhu et al, and are often hard to follow. The presented empirical results are nonetheless interesting and should be expanded upon. Here are some detailed comments\n\n- The theorems should be stated more carefully, and in particular, care should be given to make precise which constant terms are hidden away in the big-O and big-Omega notations. E.g. in theorem 2 the probability must have some dependency on c hidden away, which should be made explicit, especially given the assertion “where c can be arbitrarily small”. Similarly, in theorem 1, it is claimed that c is constant, but the theorem is only non-vacuous for either m growing or c ~ log L. There are also some typos in theorem statements (e.g. missing O in theorem 3 and lemma 3), which can easily confuse the reader.\n\n- Although I did not have time to check all the proofs, they should be treated with more care. I recommend avoiding big-O and big-Omega notations in the proofs as much as possible, as it can make some steps extremely confusing: in the proof of theorem 1, after “taking an \\epsilon-net over …”, the probability does not change despite applying an union bound! The union bound argument should be more clearly spelled out, especially given the fact that some smoothness should also be established for this argument (e.g. the trivial sub-multiplicative bound).\n\n- The empirical results are interesting, and I think could be taken even further. Indeed, the authors show promising results for learning a global scale parameter (in terms of performance), and it would be interesting to explore: 1) the value of the learned \\tau after training: is it still of the order 1 / \\sqrt{L}? Or does it take some other value. 2) whether it is better to have a \\tau per layer or one for the whole network. The presentation of the current results could be improved by including standard deviation when averages are reported, and changing figure 4 with axes starting at zero (bar charts which do not start at zero are extremely misleading).\n\n- There are also many typo and grammar issues. Although these do not seriously impede understanding, the paper could be improved by addressing those (at least running a spell-check).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1eSRY_aKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows the stability of ResNet for the output scale of resblock: $\\tau < \\sqrt{L}^{-1}$ and shows the explosion for $\\tau > L^{-0.5+c}$. Based on this analysis, a linear convergence rate of the gradient descent for the squared loss is also shown. In addition, this paper empirically verifies the efficiency of the initialization of $\\tau = \\sqrt{L}^{-1}$ with/without batch normalization.\n\nContributions of the paper are summarized below:\n- Provides a sharp characterization of the largest scale of outputs of resblocks: $\\tau$.\n- Enlarges the class of ResNets with the global convergence guarantee of the gradient descent w.r.t. the scale of $\\tau$. (A related study [Allen-Zhu+2018b] focused on the scale of $\\tau = 1/L$).\n- Improve the depth dependence in the network width and the iteration complexity compared to existing studies.\n\nSignificance:\nTo theoretically justify the success of ResNets, this line of research is important, and I think this paper makes a certain contribution in this sense, although there seems to be much room for improvements regarding the depth dependence in the network width. (Unrealistically high over-parameterization: $m=n^8L^7$ is still required). In addition, a proposed technique (Theorem 1) to derive gradient bounds is surprising and beyond the intuition. Indeed, a simple way of using a natural spectral bound cannot explain the stability of ResNets with $\\tau=L^{-0.5}$.\n\nClarity:\nThe paper is well organized but there are some technical concerns as described below.\n\nQuality:\nI think the quality of the paper can be improved. \n- Maybe probabilities in some statements are not correct, for instance, a probability in Theorem 2 should depend on the value of $c$.\n- It is better to specify the value of $c$ in Theorem 1. It may take an arbitrary small value at the expense of the probability.\n- In the convergence analysis of the gradient descent (Theorem 5), the dependency on $\\tau$ should be mentioned. Is there no effect on the convergence rate by the choice of $\\tau$?\n\nMinor comments:\n- The network architecture is different from the standard ResNets. Usually, non-linear activation functions are applied after resblocks. Can theoretical analyses be extended to such a setting?\n- Initialization scales of parameters in related studies, as well as $\\tau$, should also be clarified for a fair comparison of $\\tau$.\n- In proofs, citations of theorems and lemmas seem incorrect, e.g., Theorem 1 may be used in the proof of Lemma 3 (and Theorem 3 too?) instead of Lemma 1.\n- Typo In Theorem 1: for all $a > l$  --> for all $b > a$ (?).\n- There is no definition of $h'_{i,l}$ in Lemma 4. Is it a perturbation of a hidden node h?\n\n-----\nUpdate: \nI thank the authors for the response and hard work.\nI would like to keep my score. Some concerns have been resolved. Moreover,  I think highly of a proof technique (Theorem 1). However, the advantage of ResNets is still unclear because high over-parameterization is required.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article studies the stability of ResNets in relation to initialisation and depth. The reviewers found that this is an interesting article with important theoretical and experimental results. However, they also pointed out that the results, while good, are based on adaptations of previous work and hence might not be particularly impactful. The reviewers found that the revision made important improvements, but not quite meeting the bar for acceptance, pointing out that the presentation and details in the proofs could still be improved. 
Decision: Reject