P-BN: Towards Effective Batch Normalization in the Path Space
Authors: Xufang Luo
Qi Meng
Wei Chen
Tie-Yan Liu
Venue:  (2020)

Abstract: Neural networks with ReLU activation functions have demonstrated their success in many applications. Recently, researchers noticed a potential issue with the optimization of ReLU networks: the ReLU activation functions are positively scale-invariant (PSI), while the weights are not. This mismatch may lead to undesirable behaviors in the optimization process. Hence, some new algorithms that conduct optimizations directly in the path space (the path space is proven to be PSI) were developed, such as Stochastic Gradient Descent (SGD) in the path space, and it was shown that SGD in the path space is superior to that in the weight space. However, it is still unknown whether other deep learning techniques beyond SGD, such as batch normalization (BN), could also have their counterparts in the path space. In this paper, we conduct a formal study on the design of BN in the path space. According to our study, the key challenge is how to ensure the forward propagation in the path space, because BN is utilized during the forward process. To tackle such challenge, we propose a novel re-parameterization of ReLU networks, with which we replace each weight in the original neural network, with a new value calculated from one or several paths, while keeping the outputs of the network unchanged for any input. Then we show that BN in the path space, namely P-BN, is just a slightly modified conventional BN on the re-parameterized ReLU networks. Our experiments on two benchmark datasets, CIFAR and ImageNet, show that the proposed P-BN can signiﬁcantly outperform the conventional BN in the weight space.

Under review as a conference paper at ICLR 2020
P-BN: TOWARDS EFFECTIVE BATCH NORMALIZA- TION IN THE PATH SPACE
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks with ReLU activation functions have demonstrated their success in many applications. Recently, researchers noticed a potential issue with the op- timization of ReLU networks: the ReLU activation functions are positively scale- invariant (PSI), while the weights are not. This mismatch may lead to undesirable behaviors in the optimization process. Hence, some new algorithms that conduct optimizations directly in the path space (the path space is proven to be PSI) were developed, such Stochastic Gradient Descent (SGD) in the path space, and it was shown that, SGD in the path space is superior to that in the weight space. However, it is still unknown that whether other deep learning techniques beyond SGD, such as batch normalization (BN), could also have their counterparts in the path space. In this paper, we conduct formal study on the design of BN in the path space. According to our study, the key challenge is how to ensure the forward propagation in the path space, because BN is utilized during the forward process. To tackle such challenge, we propose novel re- pe-aamtterization of ReLU net- works, with which we replace each weight in the original neural network, with new value calculated from one several paths, while keeping the outputs of the network unchanged for any input. Then we show that BN in the path space, namely P. P-BN, is just slightly modified conventional BN on the re-parameterized ReLU networks. Finally, our experiments on two benchmark datasets, CIFAR and ImageNet, show that the proposed P-BN can significantly outperform the conven- tional BN in the weight space.
INTRODUCTION
In recent years, neural networks with rectified linear unit (ReLU) activation functiinn (abbrev. ReLU networks). have been successfully applied to many domains, such image classification (He al, 2016), game playing (Mnih et al., 2015). and text processing (Kim 2014]. Recently, it has been noticed that the feedforward neural networks with ReLU, namely ReLU networks, positively scale-invariant (PSI) (Neyshabur et al. 2015a 2016). which means when the incoming and out- going weights of a hidden node, are respectively multiplied and divided by positive constant, the outputs of ReLU networks will keep unchanged for any input. However, the vector space, composed of weights, which the conventional optimization algorithms, e.g., Stochastic Gradient Descent (S- GD), optimize the neural networks, is not PSI, and such mismatch may lead to undesirable behaviors in the optimization process (Neyshabur et al. 2015a).
To tackle such challenge, some recent studies have shown that, one ReLU network can be opti- mized in completely new PSI parameter space, i.e., the path space, instead of its original weight space (Meng et al. 2019). Detailedly, while regarding ReLUU networks as directed acyclic graphs (DAGs), we can caleulate the outputs of ReL.U networks by using path-values, i.e., the multiplication of weights along each input-output path in the DAG. Here, path-values are invariant to the positive rescaling of weights, which exactly matches the PSI property ReLU networks, and the optimiza- tion algorithms (e.g., SGD) in the path space (i.e., the vector space composed of aath-values), shown to be superior to those in the weight space (Neyshabur et al. 2015a 2016 Meng et al.) 2019).
There are already some optimization algorithms developed in the path space, however, to the best of our knowledge, is still unknown whether other deep learning techniques beyond SGD, can also have their counterparts in the path space. For example, BN is one of the most widely used normal-

---

Under review as a conference paper at ICLR 2020
ization approaches (loffe & Szegedy 2015 Santurkar et al. 2018). and is crucial for facilitating the training process of neural networks. With the help of BN, the training process of neural networks can be accelerated, by both decoupling the scale and direction of weight vectors Arrra et al. 2018) and smoothing the optimization landscape (Santurkar et al. 2018).
In this paper, conduct formal study on the de-
sign of BN in the path space. First, it is known that, BN is successfully utilized during the forward pro- cess in the weight space, but how to ensure the for- ward propagation still remains unclear in the path space, i.e.. the way to calculate the outputs of hid- den nodes via path-values layer by layer is unknown. For example, in Fig. [1] we show network and its outputs calculated by both weights and path-values. Here, the outputs of this network can be simply cal- culated by using valuesa because a path starts from input node and ends up with an output n- ode, and the path-value is just the multiplication of weights along this path. Nevertheless, the outputs of hidden nodes cannot be calculated by path-values in this obvious way. Thus, solve this problem, we propose a re-prrameterization for the weights in Re- LU networks, which can replace each weight in the original network, with a new value calculated by one or several path-values, and the outputs of the re- re-parameterized network will keep unchanged for any input. Therefore, the forward propagation in the path space can be easily conducted after ee-parameterizing the network.
Input x;
Hidden
Output
Ofi
W1
Ws
We
We
Calculate with weightts
f1 - ReLU (ii. k W ReLU X2Wl
(a.W.ls w2
(a.WaWs + RaWAMa)
14
Ce path
f1 (a.2) + d.)x (dr1a 2224)x22
An example of an MLP network. @1 and are 1 when corresponding ReLU is activated, otherwise they are
Figure 1:
Then, we show that BN the path space is just a slightly modified conventional BN on the re- parameterized network. Considering that BN in the weight space, can make the gradient propagation more effective, we study BN in the path space from the perspective of effective propagation. In details, we apply the conventional BN to the re-parameterized network, and find that the radients will explode during the backward propagation in the path space. Thus, we propose a novel BN in the path space, namely P-BN, which slightly modifies the conventional BN, via excluding the term whose coefficient is fixed by re- parrameterrzzttoon from normalization. Particularly, we theoretically prove and experimentally show that compared with the conventional BN, P-BN can propagate gradients in the path space more effectively.
Finally, we conduct extensive experiments multiple datasets, including CIFAR, ImageNet, with multiple network structures, including ResNet and PlainNet. The results demonstrate that the P-BN based optimization algorithms can significantly outperform the ones with the conventional BN.
2 BACKGROUND
2.1 RELATED WORK
In recent years, some researchers have conducted many theoretical studies on the path of ReLU net- works. On the one hand, in terms of optimization, for example. Neyshabur al. (2015a) proposed a new regularization term, i.e., path-norm, and the Path-SGD algorithm for minimizing the regular- ized loss. Meng et al. (2019) proposed G-SGD algorithm to directly optimize the model in the path space, by utilizing the gradients w.r.t. path-values. On the other hund, in terms of generalization, for example, Neyshabur et al. (2015b) and ZZenng et al. (2018) gave the relationship between gen- eralization error and path-norm or basis path-norm, respectively. Besides, E et al. (2018) leveraged the path representation of ReLU networks, to analyze the generalization error of them.
However, the aforementioned studies have not involved normalization approaches (Ba et al. 2016 Wu & He| 2018), such as BN (Toffe & Szegedy 2015), which are proved to be much crucial for for ReLU networks, BN is especially widely used in computer vision domain (He et al.) 2016 Li et al., 2016 Huang et al. 2017). Furthermore, there are also many theoretical studies on BN (Santurkar al. 2018 Arora al. 2018 Kohler al. 2019).
training neural networks. In particular,
2

---

Under review as a conference paper at ICLR 2020
Accordingly, based on the studies optimizing ReLU networks in the path space. and the crucial normalization technique, i... BN, in this paper, we will give a formal study on designing BN the path space. We will next briefly introduce the optimization of ReLU networks without BN in the path space.
2.2 OPTIMIZING RELU NETWORKS IN THE PATH SPACE
In this subsection, we introduce the feedforward ReLU network and the optimization algorithm in the path space.
Input
Hidden
Output
Firstly, as shown in Fig. 2 consider an L-layer feedforward ReLU network without BN whose weight matrices are {w<; L.... LL). we use O = 0, ... L to denote the j-th node the 1-th layer. Based these above,
further use udsa to represent the weight the edge which connects O and O3. As for the outputs of hidden nodes, suppose that given a d-dimensional input i = (rr,....a))) then the output of Oj and the hidden vector in the 1-th layer, can be denoted as of (ar) and o' (z), respectively. Thus, the outputs can be propagated as (z) = (x)), where g(-) max(:, 0) is ReLU activation function.
1y
Figure 2: An example of a feedforward ReLU network.
Secondly, will show the concept of a path in ReLU networks, and briefly introduce the optimiza- tion algorithm in the path space. In details, regarding the network structure as DAG consisting of nodes and edges, path can be defined as: list of nodes or edges, starting from an input node, suc- cessively passing by several hidden nodes along the edges, and finally ending up with an output node. For example, in Fig. 2 path starts from O2, passes O and Oi, and ends up with O3. And then, the path-value of path p can be defined as multiplication of the weights along p. i.e., 1/p w Therefore, output of (Ir) can be calculated by using path-values as of (x) = - Eper.. "y Op Th- Here, P is set which contains the paths staring from 0 and ending up with Of, and ap, the ReLU activation status of path p. can be calculated ap =lo' Ex 110 (x) > 0), where 0 represents
that O'r is passed by p.
3p
As for the optimization algorithm, introduce typical ones, i.e., Path-SGD (Neyshabur al. 2015a) and G-SGD (Meng et al. 2019). Path-SGD is to add new regularizer, i.e., path-norm, into the loss function, and then heuristically utilizes a coordinate- wised solution for minimizing the path- norm regularized loss. It is shown to be superior to SGD for MLP, but with huge computational costs when applied Convolutional Neural Networks (CNNs), due to the complicate correlations among path-values. Besides, Path-SGD only utilizes the PSI property to propose the regularizer, but cannot optimize the network in the path space. Comparatively, G-SGD can solve the computation problem, by decoupling correlations between path-values. Besides, G-SGD optimize the network via updating valu-values by using gradients w.r.t. them instead weights. Thus, G-SGD can serve as the SGD in the path space, and the detailed G-SGD are listed in Appendix
3 To DESIGN BN IN THE PATH SPACE
In this section, we first introduce re- parameterrizaiion process, to ensure the forward propagation in the path space, and calculate the outputs of hidden nodes by using path-values. Then, we will show that the conventional BN cannot effectively propagate the error signals in the path space, which calls us to design an effective BN in the path space.
3.1 RE-PARAMETERRIZATION
In this subsection, we introduce a re-parameterization for the parameters of ReLU networks, which can replace each weight with a path- value or ratio of path-values, and the outputs of the re-
For ease of presentation, only discuss the ML. with equal width, and in this paper, the analyses and algorithms be applied to the MI. and CNN with unequal width (cf. Appendix D.I.
3

---

Under review as a conference paper at ICLR 2020
Output
Wit
W22
WE
222
MESME
who
w1 mil wish Wiliww
Input
X1
4/
Rescoling Operction
Step
Step
Weight Layer indix
Node Layer Indax
Rolated Rescaling Scalar
Rolated Rescaling Hidden Node
Figure 3: An example to demonstrate the re-parameterization process for an MLP.
parameterized network will keep unchanged for any input. First of all, we present the process of re-parameterization Theorem 3.1
Theorem 3.1 Consider L-layer ReLU network with weight matrices (w/:1 1,... L}, if the diagonal elements in matrix w', > 2 are positive, the hidden outputs of the ReLU network can be calculated by using path-values follows:
(x) =
Σ
Uikk Ik
for 1=
(1)
Uya of (()) for 12 122. Uhk
(x) (x) k=1,
(2)
Here, g(-) denotes the ReLU activation function, and vie is the path-value of the path which only contains the k-th diagonal elements in the weight matrices, i.e., vēa -Il who and ejank k is the path-value of the path which contains one non-diagonal weight, ie., 1'sx = (Ila whe) ) wyye (Ls w'g))
Proof: Based on the PSI property, will prove Theorem 3.1 by designing re-parameterrizatin process which consists several weight rescaling steps. After these steps, the ReLU network can be equivalently re- re-paramtterized which means that the outputs will keep unchanged for any input after re-parameterization. Here, we will next demonstrate the re-parameterization process by showing that it can conducted for a 3-layer MIP, as well as generalized multi-layer setting-
As for 3-layer MLP, the process is shown in Fig. 3 and described in the following two steps: (1) The weights connected with nodes 03. = 1, 2 are rescaled, i.e., the incoming and outgoing weights of node Of are multiplied and divided by w respectively. To be specific, w w and whi wf2 divided and multiplied by wit and similarly, w w and w2,, we are also rescaled
by using w According to the definition of a path value, we have w wi " =
"i
" siz, and hence, each weight the 3rd layer can replaced by a constant ratio of "ie 32
path- vath-values. (2) The weights connected with nodes Of.j = 1, are rescaled, i.c., the incoming and outgoing weights node 03 are multiplied and divided by the corresponding outgoing diagonal weight (i.e., w ")) Afterwards, each weight in the middle layer can be replaced by constant or ratio of path-values, and each weight in the 1st layer can be replaced by path-value. Therefore, each weight in this network are replaced by a path-value or a ratio of path-values.
As for a multi-layer setting, the re- ce-araametrrzzation process similar that of a 3-layer MLP. In particular, this process can be proceeded by rescaling weights orderly, from which is connected with the nodes in the last hidden node layer to the first hidden node layer, and the scalar of the rescaling operation at each node, is the corresponding outgoing diagonal weight. After such rescaling steps,
the weights can be re-parameterized as follows: (1) wIe 1. # k.
Us4s (2) w 1; (3) w/y
" _ +
4

---

Under review as a conference paper at ICLR 2020
In summary, network with weight at each edge (e.g.. Step 1 in Fig. parameterized into another network with path-value or a ratio of path-values at each edge (e.g,, Step 4 in Fig. 3), by rescaling its weights layer by layer. After the pe-paaametrrization, the outputs of hidden nodes can be calculated by using path-values, in the same way as they are calculated by weights, and hence, Theorem 3.1 established.
be equivalently
The positive constraint is not essential for proving Theorem 3.1 because when the di- agonal weights are negative, the re-parameterization can still be conducted correctly by using the absolute value of the corresponding weight as the rescaling scalar. Considering the robustness and computational efficiency. this constrain exists in the optimization algorithm (Meng et al.) 2019). and hence, we follow it. Besides, this constrain will not bring much influence on the model expressive- ness, because the number of the constrained weights tiny, compared with the total weights. More- over, we discuss some other choices on the e-paraaeterization and the influence in Appendix
Remark:
3.2 ANALYZING THE BN IN THE PATH SPACE
With the re-parameterization in Section 3.1 the forward propagation can be ensured in the path space, and the outputs of hidden nodes can be caleulated by using path-values. Hence, in this subsection, we will design BN in the path space, via applying and analyzing the conventional BN to the re-parameterized network.
Firstly, we briefly introduce the conventional BN. Given mini-batch of inputs {u²; = 1,... .,), BN can normalize each output of the hidden node as (o)(()))) = ~/- of )((=")-)) + 3). where n²
of
T E. (x²) and of / 2. (o) 1²)² + represent the mean and standard deviation of the minibatch outputs, and 2/. B) are the scale and shift term which are independent with w, respectively. Then, we can denote the output after BN and ReLU as 2) (xx) = 9 (BN (BN(()((z")))
Secondly, we analyze the gradient propagation in the re-parameterized network with the the conven- oc
denote the cross-entropy loss and the gradient vector w.r.t hidden output in layer L, respectively. Then, we can give an estimation of the norm of V Vir(wr) C in Theorem 3.2.
tional BN. Here, we L and V (u+( ae (2)) de (ar))
Theorem 3.2 We use Wif to denote the parameter matrix in layer I after the re-paramettrizattion. Suppose (x²) < O(1), Vi,j, 1, and m > 64. The norm of the grudient w.r.t 2x(x²) can be upper bounded as
fi [ (0) will
IV 17 C11 S
where a' diag(oi, ..)....,)) o'' = ddigg(i.... rdd, and D' diag( Di (a").... Daa(=")) Here, diag(ar (11. ................................ aa) represents a diagonal matrix whose diagonal elements are ai, as and (a))))) = 1 if (x²) > 0, otherwise (2'x') =0.
The proof of Theorem 3.2 can be found in Appendix B
According to Theorem 3.2 the gradient norm exponentially depends on depth L. the spectral norm of matrix D²(x") . (a.)-1 W roughly equals to the error signals can be effectively propagated in the backward process (i.e., not vanished or exploded). On the one hand, there non-zero elements in D* its spectral norm will equal to 1. On the other hand, in practice, to be 1. and will keep its value around 1 during the training process, so the spectral norm of 72 will be around 1. Hence, the magnitudes of W/ and o is crucial for the gradient norm. For matrix W according to Theorem 3.1 the diagonal elements of Ws 2 2) are degenerated be constant 1, and these constant terms will not be trained. Besides, the trained parameters are initialized to be much smaller than 1 (cf. Appendix D.3). so matrix W will approach to an identity matrix. For matrix o. 1 if each of is smaller than 1, it can cause gradient exploding during the back propagation process. We will conduct observational experiments in Section 5.2 and it shows that ||a*|| is less than 1 and gradients becomes larger during the back propagation process.
Discussion:
of is initialized
In the following analysis, referring to Santurkar et al. 2018), assume that hoth of the scale and shift
term constant.
5

---

Under review as a conference paper at ICLR 2020
Therefore, such discussion result motivates us to design BN in the path space by modifying the conventional BN, in order to propagate the error signals effectively. We will next detailedly introduce the proposed BN in the path space, i.c,, P-BN.
4 P-BN: EFFECTIVE BN IN THE PATH SPACE
In this section, we design the BN in the path space, namely P-BN, via slightly modifying the forward process of the conventional BN. Motivated by the calculation for the outputs of hidden node in Theorem 3.1. as well the discussion of Theorem 3.2, propose to normalize the terms related to the trained coefficients (i.e., Eq. [ and the 2nd term in Eq. 2) and exclude the term related to the constant coefficient (i.e., the 1st term in Eq. 2). Specifically, we use (x²") to denote the output after P-BN and ReL.U, and detailedly describe the forward process of P-BN in the following two steps.
(1) For the 1st layer, the operation of P-BN is the same the conventional BN, i.e., (x²) = (=))
(2) For the I-th layer 2 2), as shown in Fig. there are three sub-steps for P-BN as follows.
First, calculate the partial weighted summation. Here, the in- put related to the diagonal constant element in the parameter matrix is excluded, i.e.,
BN
P-BN
ZZ
Z
Σ
(x)
1=1,
Mean
BN
Variance of
Second, normalize the partial weighted summation above, i.e.,
Mean
BN(() (x = 2/ of' (x') - w// + 8
Variance oi
(4)
1
o
i
Third, add the excluded term 2j (x') into the normalized par- tial weighted summation in Eq. i.e..
(a))
Figure 4: An example of the 2nd step in P-BN.
Σa(0') = (BN(d) (z)) +x)
(5)
Consequently, P-BN can be easily combined with the opti-
mization algorithm in the path space for ReLU networks, and we will show it in Algorithm ! in Appendix E
Then, we will show that the gradients can be effectively propagated by using P-BN in Theorem
Theorem 4.1 Suppose xx(x') < O(1), vi, and m 64, the norm of gradient w.n. z (x") can be upper bounded as
1. IIV 1 50
(x')))((1+) (0t-1=2.W.))
(=1++1
where W/ Wi Ihi diaglo!! .... o'l),, ntd diag(s) ... ,aaa and D (x") where D, - (x²) > O, otherwise (1, =0.
The proof of Theorem 4.1 can be found in Appendix B Then, give Corollary 4.2 via summariz-
ing from Theorem 3.2 and Theorem
Corollary 4.2 Using the notations in Theorem 3.2 and Theorem 4.1 and initializing y' and 7f to
be identity matrix, we have the following upper bound for gradient norm at initialization point
1.
|| # (r
50
II
*11+1
4.
V
11 +=++1
(x')
(1+(0)))))

---

Under review as a conference paper at ICLR 2020
PlainNet
ResNet
Dataset
Method
6.93% (+-0112)
(4-0222)
6.76% (+0.10)
6.40% (++0.09)
(40.24)
G-SGD+BN
6.66% (+0.
6.74% (#0.13)
6.84% (=0.30)
6.54% (+0.06)
6.62% (#0.19)
CIFAR-10
G-SGD+BN (wnorm)
6,26% (1:0.17)
6.67% (#0.26)
6.31% (=0.14)
6,33% (20.11)
6.31% (#0.144
G-SGD+P-BNN BN
5.99% (100.13)
6.04% (100.6)
6.04% (10.144)
5.66% (1.0.10)
5.99% (10.12)
SGD+BN
28.10% (:10.19)
33.37% (:00.41)
26.97% (1:0.12)
26.42% (2:0.23)
25.62%
(=0.18)
G-SGD+BN
27.08% (+:0.35)
28.19% (d:0.35)
27.13% (4:0.39)
26.61% (=0.10)
25.99% (=0.40)
CIFAR-100
G-SCIDBBN
26.76% (2:0.05)
27.61% (4:0.24)
26.60% (2:0.17)
26.72% (220.27)
25.65%
(-2.22)
G G-SGD+P BN
26.70% (1.0.10)
(1.0.12)
(100.10)
26.24% (10.29)
25.29% (10.19)
Table 1: Test error rate on CIFAR- 10 and CIFAR-100.
2.03
50 Bi
0.76
BN
P-X
Stantaa 1 Devatten
3
2.75
200 p- en
2.30
ScDv
0.72
23.25
0.79
0.75
0.68
-35
Fpoch
Epwc
Layer Index
Layer Inde2
Figure 5: Curves for training ImageNet.
Figure 6: Experimental observations.
(wt) Gll can be upper bounded by constant (i.e., will not diverge as L is E ((1+)) L(++)] Vj. respectively.
Suppose [[W||- A sufficient condition for that |I VV9221 and V
and of (AL, L-1
2// is much larger than that Discussion: We can conclude from Corollary 4.2 that the range for oj"
for of. Furthermore, if A S 1. we have [i1+x - C oo), (i.e., the range for of is fully 1.41
contained in the range ), which indicates the backward stability of P-BN. We will observe the variance in each layer in Section [5.2] and the results demonstrate that the variance becomes larger with P-BN. Thus, to some extent, the gradient propagated more stable for NN with P-BN.
5 EXPERIMENTS
In this section, we conduct experiments by first comparing the performance of P-BN with the base- lines on various datasets with some network structures, and then showing some experimental obser- vations to support theoretical analyses.
5.1 PERFORMANCE EXPERIMENTS
In this subsection, we evaluate the performance P-BN on training deep neural networks by con- ducting experiments three datasets, CIFAR-10, CIFAR-100, and ImageNet. We will next intro- duce the network structures and compared methods first.
5.1.1 NETWORK STRUCTURES AND COMPARED METHODS
In this subsection, we describe the network structures and compared methods. First, as for the network structures, apply P-BN to train ResNet and PlainNet (He et al. 2016). Second, show the setting details of four compared methods as follows.
We SGD to train the network with the conventional BN. (2) G-SGD+BN: We use G-SGD to train the network with the conventional BN.
(1) SGD+BN:
(3) B-SGD=BN(wnorm): We use a method which was intuitively proposed handle the conven- tional BN without any theoretical analysis (Meng et al. 2019). Here, the gradient of the path-value,
Pleasse note that the conditions are tight in the sense that if change T. in the ranges to be T!!-s, the upper bound of both the gradient norm for BN and P-BN will diverge.

---

Under review as a conference paper at ICLR 2020
is normalized by the L2- of the weights pointing the same hidden unit. (4) G-SGD+P-BN: Our proposed P-BN targets on BN in the path space, and the network with P-BN should be optimized by the algorithms in the path space. Thus, use G-SGD to train the network with P-BN..
5.1.2 CIFAR
We conduct experiments on CIFAR-10 10 dataset and 2009). Here, we train ResNet of 18, 34, and 50 layers, and PlainNet of 18 and 34 layers, respectively. As of methods mentioned
CIFAR- dataset (Krizhevsky
Method
Metric
ReaNet
SGD+BN
G-SGD+P-BN
27.34% (=00.0)
25.92% (++0.18)
for the hyper-paramene in their corresponding papers, i.e., SGD+BN (He et al... 2016) and G-SGID+BN(wnorm) (Meng et al. 2019). we use the same settings as their original ones. Besides, we tune the dyper-parametent for other methods, i.e., G-SGD+BN, and the proposed F-SGD+P-BNN More details about the experimen- tal setting can refer to Appendix(E1 F. Table [ we
Top Test Frror Rate
101
25.94%
(=0.09)
24.36%
(=0.10)
152
25.65% (=0.15)
23.91% (=+0.23)
50
9.10% (+00066)
8.26% (+H0.16)
Top Test
8.33% (#0.07)
7.43% (+0.05)
Error Rate
152
8.31% (=00.9)
7.25% (20,09)
Table 2: Test error rate on ImageNet.
show the performance results the test error rate, and in Fig. 8 plot the training curve and test accuracy of 50-layer ResNet. Such results demonstrate that: (?) G-SGD+P-BN outperforms others on all tested datasets and network structures, which shows the superiority of P-BN: (2) Combining the path space and the conventional BN directly hurts performance, which empirically motivates us to propose P-BN; (3) G-SGD+P-BN outperforms (-SGD+BN(wnorm)) which shows the benefit and significance of our proposed formal analyses.
5.1.3 IMAGENET
We conduct experiments ImageNet dataset (Russakovsky et al. 2015). Here, we train ResNet of 50, 101 and 152 layers, to demonstrate that the proposed P-BN can help to train very deep networks on large dataset, and we compare the performance results between SGD+BN and G-SGD+P-BRR and more details can
The method for tuming the
is similar to that in Section refer to Appendix F.I In Table 2 we list top-1 and top-5 test error rates, and in Fig. 5 plot the training curve and test accuracy during training ResNet of 50, 101, and 152 layers. These results well demonstrate the superiority of G-SGD+P -BN, and show that for the large dataset and very deep networks, P-BN can still outperform the conventional BN.
5.2 OBSERVATIONS ON STANDARD DEVIATIONS AND GRADIENTS
After analyzing the advantage of P-BN over the conventional BN theoretically in Section 3.2 and 4 now provide some experimental observations to support analyses. Here, we will show the magnitude of standard deviations in BN, and the gradients of ReLU networks with BN and P-BN.
In this experiments, CIFAR-10 10 as training data, with the batch size of 128. Then, we add the conventional BN or P-BN the end of each hidden layer in the stacked CNN, which is denoted as BN and P-BN, respective- ly. For the model with the conventional BN, it is randomly initialized. For the model with P-BN, the diagonal elements in parameter matrices (expect for the 1st layer) are initialized to 1 (cf. Sec- tion B.1. and other elements are initialized with small random values (cf. Appendix D.3). Because the theoretical analyses are not related to the training process, we will just observe some quantities at initialization as follows.
stacked CNN of 50 layers with 128 channels in each layer, and use
First, we show some observations on standard deviation of in Theorem 3.2 Here, we log oj for each hidden node during the forward process of the /st mini-batch, and then calculate the average standard deviation among the nodes in each layer. In Fig. 6 we plot the curves regarding standard deviations, and we can observe that: (1) For the conventional BN, the standard deviations are smaller than 1, which matches the claim in Theorem 3.2 and is one of the reasons of the gradient exploding. (2) For P-BN, the standard deviation grows when the layer index becomes larger, and most of them are larger than 1. Thus, in Theorem 4.1 ||o,-1 WIll are smaller than [|/]] and || (Ill can be upper bounded, which is one of the reasons for that the gradient exploding can be weaken by P-BN.
8

---

Under review as a conference paper at ICLR 2020
Second, we show some observations gradients, investigate that whether the gradient exploding can be weaken by P-BN in practice. Here, we log the L.- -oomoomm of gradients of loss w.r.t the outputs in each layer, and plot the log of the gradient norm in Fig. 6 We observe that, the gradients indeed explode in the ReLU network with both the conventional BN and P-BN, and the exploding speed is much slower with P-BN, which demonstrates that P-BN can help to weaken the gradient exploding.
6 CONCLUSION
In this paper, we conduct a formal study on the design of BN in the path space. First, considering that BN is adopted during the forward process, we ensure the forward propagation the path space, via proposing a re parameterization for weights in ReLU networks. Here, the paraamtterizztion can equivalently replace each weight in the original network with a new value calculated by one or several path-values, and hence, the outputs of hidden nodes be calculated by using path-values. Then, we design BN in the path space, by applying and analyzing the conventional BN to the re- parameterized network. Here, we analyze the gradient propagation after BN applied, and then notice that the gradient will explode in such networks. Thus, we propose a novel BN in the path space, i.e., P-BN, which excludes the term whose coefficient fixed by re- pe-aaamterizztionn from normalization. Finally, we conduct experiments to verify the proposed method, and results on both CIFAR and ImageNet dataset, demonstrate that P-BN can enhance the performance significantly.
REFERENCES
Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis of auto rate-tuning by batch normalization. arXiv preprint arXiv:1812.03981, 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint arXiv:1607.064500 2016.
Weinan E, Chao Ma and Lei Wu. A priori estimates for two-layer neural networks. arXiv preprint arXiv:1810.06397.. 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks, In CVPR, volume pp. 3, 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, pp. 448-456, 2015.
Yoon Kim. Convolutional neural networks for sentence classification. iv: nel1408.5888 2014.
arXiv preprint arX-
Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann, Ming Zhou, and Klaus Neymeyr. Exponential convergence rates for batch normalization: The power of length-direction decoupling in non-convex optimization. In AISTATS, pp. 806-815, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yanghao Li. Naiyan Wang, Jianping Shi, Jiaying Liu, and Xiaodi Hou. Revisiting batch normaliza- tion for practical domain adaptation. arXiv preprint arXiv: 1600.04779, 2016.
Qi Meng, Shuxin Zheng, Huishuai Zhang, Wei Chen, Zhi-Ming Ma, and Tie- Yan Liu. G-SGD: Optimizing ReLU neural networks in its positively scale-invariant space. In ICLR, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.

---

Under review as a conference paper at ICLR 2020
Behnam Neyshabur, Ruslan Salakhutdinov, and Nathan Srebro. Path-SGD: Path-normalized opti- mization in deep neural networks. arxiv preprint 1rX.v:1506.02617, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In COLT, pp. 1376-1401, 2015b.
Behnam Neyshabur, Yuhuai Wu, Ruslan R Salakhutdinov, and Nati Srebro. Path-normalized opti- mization of recurrent neural networks with ReLU activations. In NeurlPS, pp. 3477-3485, 2016.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary VeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NeurlPS-W.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. ImageNet large scale visu- al recognition challenge. IJCV, 115()):11-222, 2015.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normal- ization help optimization? In NeurlPS, pp. 2483-2493, 2018.
Yuxin Wu and Kaiming He. Group normalization In ECCV, pp. 3-, 2018.
Shuxin Zheng, Qi Meng, Huishuai Zhang, Wei Chen, Nenghai Yu, and Yan Liu. Capacity control of ReLU neural networks by basis-path norm. arXiv preprint arXiv:1809.07122 2018.
10

---

Under review as a conference paper at ICLR 2020
A
NOTATIONS
Notation
Object
d-dimensional input, i.c., a (21, (
Minibatch size
Weight matrix in the I-th layer
(x)
Output of the j-th hidden node in the 1-th layer
o'(x)
Hidden vector in the (-h layer
Weight the edge which connects the k-th node in the (t 1)-th th layer and the j-th node in the 1-th layer
Path-value of the path which only contains the k-th diagonal elements weight matrices, i.c., ubs = IT weR
US k f
Path-value of the path which contains non-diagonal weight, i.e, e/e (Tl.rt whe) wie (II,sI w(y))
(x)
Output after BN and ReLU of the j-th hidden node in the 1-th layer
(x)
Output after P-BN and ReL U j-th hidden node in 1-th layer
W/
Parameter matrix in layer after the parameterization.
1
Mean of the minibatch outputs of the j-th hidden node in the 1-th layer
Standard deviation of the minibatch outputs of the j-th hidden node in the I-th layer
Table 3: Main notations in this paper.
B SUPPLEMENTARY PROOFS
Theorem B.1 We Wi denote the parameter matrix in layer after the re-parameterization.
Suppose 2/(x²)) < O(1), j, and the batch size m >> 64. The norm of gradient w.r.t 2 (x(x) can
be upper bounded as
( ( [I'((')) (0")- .W:l)
VV Cll S o
where o' diaglol..... ... o.)) 7' diag(Th.... wh and D'(x") = diag( diag((D(("))) (at).... Da((e)), Here, diag(an, ... aa) represents diagonal matrix whose diagonal elements are an,... (d, and (x²)) 1 if 2) (x²) > O, otherwise (xx(=))= =0
We concat the gradient vector of different instances in a minibatch into one (d x m)- dimensional vector as
Proof:
ci C (V (ol( ())
and hence, according to chain rule, we have
dzL dok dot. dzh-1" Oz!
0olt1
V V V
Here, the hand, for matrix
0z Bor
it donates
dz (ac))
(=
(
0z
a
(z')
do
do
Do (ar)
0g²
8a [x)
def(a

---

Under review as a conference paper at ICLR 2020
So have
0zf(x²)
1
(x)()"))²)
if j2 and i1 = -i = =;;
(9)
(of(x²)
of
0zg(a"))
22
1
Dz(11))
(-
23(x²)
2))) if j2 j and it + i2; (10)
00f(1t)
0j
Ozf, (xth)
0, j1 + j2.
(11)
00j, (1t2)
Obviously, most of the elements the matrix equals to zero. Under the assumption that (x') < (1) for all j, and m > 64, the above matrix approaches to the diagonal matrix D -7" (o+)-1
On the other hand, as for matrix 85
go
it donates
W
0
0o
W
(12)
02*
W
Thus, using the fact that ||AB|| - ||||||]| we can get the result in the theorem.
Theorem B.2 Suppose (x"x) ((1), Vi, H, and m > 64. The norm of grudient w.r. E (xo) can be upper bounded as
II (1)
II
1
D (1 (1+ (001)"' - .w'II
where W/ W 1, dy! diaglo' .... ,',,,,,)))))))) o1 The = diagl?! .... ,28/ and D D((2')
diag( (x"),, ... 3 Da(a')) where (5('') = (x²) > 0, otherwise (=(x=)== = 0.
Proof: According to the chain rule, we have
0=
03
0o/+1./
02 0z 1+1
V C = Veeh C.
+
(13)
D...//
02"-1
0z
L-1
0z
T--1
02
0z
where 0 0
denotes
do (at)
dog (wl)
Do (zm)
02j(x²)
0=)(=))
000 (a))
dop (zl)
00 (zm)
(14)
Do
(
(
0o (a+)
/ (xl)
do (zm)
So have
(x)(
=
D,(0))
35
(1
(BN(o) (xt))²)
if = j2 = and 11 = i2 = i;
0o (xt)
m
m
(15)
(x"))
Dj (2+1)
33
1
1 (0 (x
(x²²)))
0oy. 3// (0/2)
0
m
m
if j2 j and # fz; (16)
05' (x
= =0, if # ju-
(17)
00 2/ (xts)
12

---

Under review as a conference paper at ICLR 2020
Obviously, most of the elements in the matrix equals zero. Under the assumption that Z (x*)) is bounded for all j, I, the above matrix tend to be the diagonal matrix D -'")"-(o")~ m approaches
On the one hand, as for matrix Da we have
0 0z
1.
(18)
Do
On the other hand, as for matrix
we have
85
W
0or
0
W
(19)
0="-1
W
Thus, using the fact that ||AB|| I ||| we can get the result in the theorem.
C DETAILS ON OPTIMIZATION ALGORITHMS IN THE PATH SPACE
We provide the detailed update rules on G-SGD Meng et al. 2019 in this section. Here, we use wy and to denote the diagonal weight and non- con-diagonal weight at layer 1, respectively, and use wy and Wy denote the diagonal weight and non-diagonal weight at layer 1, 2, respectively. The gradient of w w.r.t loss I, can be represented by ów Then we have
6',, w Em, +w,, owg, we
w wft1 = w/
w = w
(20)
w
w/y - 1/: 8t (wg))
++1 = w 5m.,, w w
++1
(21)
I(w, + we) wi ++1
/wa
where event wy wy, means wj and wy contained in one of the paths, containing one non- diagonal weights at most.
D DISCUSSION ABOUT REPPARAMETERIZATION
D. UNEQUAL WIDTH MLP AND CNN
In this section, we first show the method for finding weights used for rescaling in Theorem 3.1 which denoted as "red weights" here, for the network with unequal width of the input and output layers.
Input
Hidden
Output
As shown in Fig. 7, for weight matrix {w':l 2, L 1}. the diagonal elements are selected as red weights. For weight matrix w² and w with size (D, ha) and (h,-1,K), where D and K are number of input and output nodes, respective- ly, and l; is the number of nodes in the i-th hidden layer, then, elements {wi (i mod D, f): 1,... h.. and {i, mod =) h are selected as red weights, respec- tively.
Figure 7: An example of feedfor- ward ReLU network.
Besides, all methods can be easily applied to CNN. As we all know, a filter in CNN transforms input feature map to the output feature map. Thus, each feature map can be regarded as a hidden node in MLP. and then the filter connects two feature maps in CNN corresponds to the weight connects two hidden nodes in MLP. Besides, the method identify red weights is similar with that for MLP unless the diagonal elements the 4-triple of the weight matrices are selected. Suppose the 4-triple of weight matrices is 664, 64, 3, where the first two elements denote the number of
13

---

Under review as a conference paper at ICLR 2020
input channels and output channels, the last two elements denote the size of filter. The element [0, 0, 1,1), 1, 1]. [2, 2, 1, 1.,...... [63, 63, 1, 1] are selected to be red weights. In this way, the re- parameterization method in Theorem 3.1 is easy to extend to CNN by rescaling the weights using the selected red weights.
D.2 OTHER CHOICES ON RE-PARAMETERIZATION
In this section, discuss other choices e--paammttrrzzation and the influence. The parameterization method using path-values showed in the proof of Theorem [.1 is not unique. For example, obtain another kind of re-parameterizattin,, via multiplying and dividing the incom- ing and outgoing weights of O by o in step 4 of Figure This will not influence analyses much in this paper for the following two reasons. First, whatever re- parameterization method used, each parameterized network can serve as sufficient representation for ReLU networks in the path space, because the outputs of the network will keep unchanged for any input after re- re-parameterization. Sec- ond, our studies are based on Theorem 3.1 which can be generalized to other re- p-parameterization methods.
D.3 RELATIONSHIP BETWEEN RE-PARAMETERRIZAIION AND OPTIMIZATION PROCESS
In this section, we show how the network should be optimized after it has been re- re-parameterized. Specifically, after re-parameterization, we can optimize the loss function according to gradients with respect to the path-values using the optimization algorithm such as SGD as follows. First, we denote the parameter matrix the re- re-parameterized network at the I-th layer as W/, whose elements constant, path-value, and ration of path-values. Next, the gradient of Wy. According to the chain rule, for the path-values that will not appear in the denominator, its gradient be calculated as:
use back propagation to obtain
(22)
Ukk
and for the values that will appear in the denominator, its gradient can be calculated as:
Vw! w/: E==1k=1 Vul.
VoL. c
(23)
Uk
Then, derive the update rule of SGD in path space mentioned in Section Here, please note that the update rules derived from oe-praametrizzation is consistent with that provided in (Meng al., 2019), and parameterization provides much simpler and straightforward way to explain the complex update rules.
Based the process above, now provide Specifically, for the 2nd term Eq. [3 the numerator contains many terms, which tends to be larger than the gradient of other paths, and thus, the denominator, i.c., vie, 1. .d) is initialized be large in practice to match the magnitude of the numerator. Therefore, for the parameter matrix W/, vhe (A= = 1.... d) appears the denominator for most of its elements, and hence, these elements are initialized to be much smaller than 1, which supports analyses in Theorem 3.2
analyses the magnitude of parameter matrices.
E FULL ALGORITHM FOR OPTIMIZING RELU NETWORKS WITH P-BN
we show the full algorithm for optimizing ReLU networks with P-BN in the path space. Besides, please check more details of PathOptimizer in Section 2,2 and Appendix C
In Algorithm [
F DETAILS ON EXPERIMENTS
F.1 EXPERIMENTAL SETTING DETAILS
In particular, following the settings in Meng al. 2019), we apply G-SGD P-BN with residual blocks, because there is no positive scaling invariance across residual blocks. In addition, we intro- duce a coefficient X(A < 1) for ž (wr) in Eq. 5 for experiments of ResNet. to prevent the output exploding during the forward process, and À for all layers in ResNet is set be O.
14

---

Under review as a conference paper at ICLR 2020
Algorithm Optimization Algorithm in the Path Space of ReLU networks with P-BN.
Require: A mini-batch of inputs: = {a" ,..,,..,0 ,,",," initialization w()), and PathOptimizer.
for t 0, 1....... .T' do
Forward Process
1. Normalize the output in the /st layer in the same way the conventional BN.
for 2. do
2. Normalize the partial weighted summation by using the conventional BN according to
3]
3. Calculate the mean and standard deviation of the partial weighted summation according
to Eq. 4
4. Add the excluded term into the normalized partial weighted summation according to Eq.
end for
5. Calculate the value of loss function ((w(9) by using the final output.
Backward Process
6. Calculate the gradient of (((); (wl(w(t)) + Back Propagation (I(w(()); (())
Update Rule of Path Optimizer
7. w(+1) = PalhOplimizer(w0) V (l)(()(()))
end for Ensure: w wT
Here we describe pre pre-preeessing steps, which is same He et al. (0116). For CIFAR- 10 and CIFAR- 100, we randomly crop the input image by size of 32 with padding size of 4, and normalize every pixel value [0, 1.. Then the random horizontal flipping the image is applied. For ImageNet, randomly crop the input image by size of 224, and normalize every pixel value to [0, 1]. Then the random horizontal flipping to the image also applied.
We use 1 NVIDIA Tesla P100 or P40 GPU to run the experiments on CIFAR, and use 4 NVIDIA Tesla P100 or P40 GPUs in one machine run the experiments on ImageNet. All experiments are averaged over 5 runs with different random seeds, and Py PyTorch (Paszke et al.) is used for implementation.
Here we list of methods mentioned in their corresponding papers, i.e., SGD+BN (He et al. 2016) and (g- SGD)=BN(wnorm) (Meng et al., 2019). we use the same settings as their original ones. Specifi- cally, for SGD+BN, the initial learning rate set to 0.1, and for G-SGD+BN (wnorm), the initial learning rate is set to 1.0. Besides, we tune hyper-parameters for (G-SGD)+BN and the proposed (G-SGD)((PBB)) (P-NN). Specifically, the initial learning rate is searched from (0.1, 0.2, 0.5, 1.0). Then, use the method proposed in (Zheng et al. 2018) the weight decay in the path space, and set the coefficient of the weight decay to 10 for these two methods. Besides, we use the SGD without momentum in experiments, because the way to utilize momentum in the path space remains unclear now. Moreover, for all models and algorithms, the mini-batch size is set to be 128 and the training process is conducted for 64k iterations. The learning rates multiplied by 0.1 after 32k and 48k iterations in all experiments, and the coefficient of weight decay for methods is set to be 0.0001.
used for CIFAR-10 and CIFAR-100. As for the hyper-parameters
Here we list syper-parameter used for ImageNet. For all experiments here. the mini-batch size is to be 256 and the hyper-paramett for weight decay is set to be 0.0001 He al. (2016). For SGD+BN, the initial learning rate is set to 0.1 He et al. (2016). For G-SGD+P-BN, we only tune the initial learning rate from 0.2, 0.5). The training process is conducted for 90 epochs, and the learning rate is multiplied by 0.1 after 30 and 60 epochs.
As for stacked CNN used for observations in Section 5.2 we use the following settings: kernel size 3, stride 1, padding 1, and no bias. For CNN, the network width is the the number of channels, which is set to 128 for all hidden layers.
F.2 SUPPLEMENTARY RESULTS
In Fig. plot the training curve and test accuracy of 50-layer ResNet. Here, we add other baseline, ie.. SGD+P-BN, in which use SGD to train the network with P-BN, and in Table we show
15

---

Under review as a conference paper at ICLR 2020
PlainNet
ResNet
Dutaset
Method
34
CIFAR-I0
SGD+P-BN
7.00% (+0.08)
7.68% (+0.21)
6.78% (+0.15)
6.57% (+00066
(+0.233
CIFAR 100
SGD+P BN
28.57% (40.46)
32.98% (+-0.81)
26.71% (40.22)
26.80% (40.51)
25.68% (100228
Table 4: Test error rate CIFAR-10 10 and CIFAR- 140 for SGD+P-BN.
107
0.34
30a
Scbeeh
30-
9.32
Traking Lass
10
0562-3MMNEE
20.74
20.73
0.72
10
0.48
50
102
150
200
50
150
150
55
150
350
200
50
100
150
Epach
Epech
(a) CIFAR-10.
(b) CIFAR-100.
Figure 8: Training curves and test accuracy for training ResNet of 50 layers on CIFAR.
the test error for SGD+P-BN, We can observe that G-SGD+P-BN outperforms SGD+P-BN, which demonstrate the benefits of optimizing in the path space.
F.3 EXPERIMENTS FOR PATH-SGD
As mentioned in Section 2.2 Path-SGD (Nyshhaur al. 2015a) is another PSI-related optimiza-
tion algorithm, but not the optimizer in the path space.
First, introduce the network structure and some basic settings. Here, because Path-SGD is compu- tationally cost for CNN, follow the experimen- tal settings in (Neyshabur et af. 201 and use an MLP of 5 layers, whose number hidden nodes in each layer is 4000, and the conventional BN or P- BN is added at the end of every hidden layer. Be- sides, we use CIFAR- 10 as the training data, and the batch size set to 64. Moreover, all experiments are run for 150 epochs, and results are obtained by averaging over runs. The only hyper-parameter needs to be tuned is learning rate, which is searched from 5),-(,,),))
Method
Validation Error
SGD+BN
35.30% (#0.54)
Path-SGD
41.40% (=0.25)
Bath-GGD+BN
35.00% (=0.71)
Path- Path-SGD+P-BN
34.45% (=0.29)
Table 5: Validation error for Path-SGD exper- iments.
Then, we show the setting details of compared methods as follow:
SGD+BN: We use SGD to train the network with the conventional BN.
Path-SGD: We use Path-SGD to train the network without BN. 3
Path-SGD+BN: We use Path-SGD train the network with the conventional BN.
Path-SGD+P-BN: We use Path-SGD to train the network with P-BN.
In Table we list the validation error of these methods. Results show that: (1) BBhhSGGD+PBBN outperforms other baselines, which well demonstrate the superiority of P-BN. (2) Bith-SGD+P-BN and Path-SGD+BN perform better than SGD+BN, which show the benefits of optimizing in the path space.
WWe do not apply this setting for ResNet and PlainNet, hecause the performance will he badly hurt, and training will fail when BN removed.
16

---

Under review as a conference paper at ICLR 2020
F.4 ANALYSIS OF COMPUTATIONAL COSTS
Different from the conventional BN, P-BN is to identify the diagonal elements of weight matrices. For convolutional networks, the outputs of hidden nodes in MLP always correspond the feature maps. Hence, on the one hand, the sizes of feature maps in different layers are the same, and the stride length is I, we can then the diagonal elements in weight matrices and add skip connec- tions for all layers (except the 1st layer), which will not bring extra computational cost. On the other hand, the stride length is larger than 1, we can also set the diagonal elements weight matrices to O, and additionally, use fxed-weight convolutional layer, with only diagonal elements fixed to 1 and others fixed to O. Thus, with the skip connection or the fixed-weight convolutional layer, the back propagation process can be easily implemented. Therefore, according to the above implemen- tation, P-BN will not bring much extra computational cost compared with the conventional BN. Statistically. in our experiments, the ratio of run time between G-SGD+Path-BB and SGD+BN, is less than 3, and the extra computational cost is mainly brought by the update of G-SGD instead of P-BN.
17


Reviews:
[{"review_id": "ryeSKamyoB", "reviewer": "AnonReviewer4", "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": "The proposal is an adapted batch normalization method for path regularization methods used in the optimization of neural networks. For neural networks with Relu activations, there exits a particular singularity structure, called positively\nscale-invariant, which may slow optimization. In that regard, it is natural to remove these singularities by optimizing along invariant input-output paths. Yet, the paper does not motivate this type of regularization for batchnormalized nets. In fact, batch normalization naturally remedies this type of singularity since lengths of weights are trained separately from the direction of weights. Then, the authors motivate their novel batch-normalization to gradient exploding (/vanishing) which is a completely different issue. \nI am not sure whether I understood the established theoretical results in this paper. Let start with Theorem 3.1: I am not sure about the statement of the theorem. Is this result for a linear net? I think for a Relu net, outputs need an additional scaling parameter that depends on all past hidden states (outputs). Theorem 3.2 and 4.1 do not seem informative to me. Authors are saying that if some terms in the established bound in Theorem 4.1 is small, then exploding gradient does not occur for their novel method. The same argument can be applied to the plain batchnorm result in Theorem 3.2. For me, it is not clear to see the reason why the proposed method remedies the gradient exploding (/vanishing). \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1leWJ7TYr", "reviewer": "AnonReviewer2", "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 analyzes a reparametrization of the network that migrates from the weight space to the path space. It enables an easier way to understand the batch normalization (BN). Then the authors propose a variant of BN on the path space and empirically show better performance with the new proposal. \n\nTo study BN in the reparameterized space is well-intuited and a natural idea. Theorem 3.1 itself is interesting and has some value in understanding BN. However, the main contribution of the paper, i.e., the proposal of the P-BN, is not motivated enough. It is merely mentioned in the beginning of section 4 and it's not clear why this modification is better compared to conventional BN. This is not verified by theory either. By comparing theorem 3.2 and theorem 4.1, it seems P-BN even gives even worse upper bound of gradient norm. \nPlus we don't actually care that much about the issue of gradient exploding since one could always do gradient clipping. The notorious gradient vanishing problem on the other hand, is not address in the theorems. \nThe formulation of the P-BN seems to be closely related to ResNet, since it sets aside the identity mapping and only normalizes on the other part. It would be better to have some discussions. \nAlso, the reparameterization and P-BN seems only to apply to fully connected layer from Eqn. (3-5) where they are proposed, but the experiments applies to ResNet. It would be better to describe the method in a broader sense. How would you do this P-BN in more complicated networks?\n\nFinally, it's very unclear to me the value of Theorem 3.1 and the proof that takes almost one page in the main context. The assumption of diagonal elements of matrix w to be all positive is very restrictive and simply removes the effect of ReLU activations. \n\nTherefore I think the paper has some room for improvement and is not very suitable for publication right now. \n\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two 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": "HkxkpF_j5S", "reviewer": "AnonReviewer3", "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": "Originality: The paper proposed a new Path-BatchNormalization in path space and compared the proposed method with traditional CNN with BN.\n\nQuality: The theoretical part is messy but intuitive. Also, why P-BN helps path optimization is not clear in the paper. The experimental part is not convincing. All CNN with BN networks have much lower accuracy than people reported, e.g. https://pytorch.org/docs/stable/torchvision/models.html for ResNet on ImageNet.\n\nClarity: The written is not clear enough. It is not easy to imagine how the re-parameterization works on CNNs since the kernel is applied over the entire image (\"hidden activations\").\n\nSignificance: \nSee above.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the extension of path-space-based SGD (which has some previously-acknowledged advantages over traditional weight-space SGD) to handle batch normalization. Given the success of BN in traditional settings, this is a reasonable scenario to consider.  The analysis and algorithm development involved exploits a reparameterization process to transition from the weight space to the path space.  Empirical tests are then conducted on CIFAR and ImageNet.

Overall, there was a consensus among reviewers to reject this paper, and the AC did not find sufficient justification to overrule this consensus.  Note that some of the negative feedback was likely due, at least in part, to unclear aspects of the paper, an issue either explicitly stated or implied by all reviewers.  While obviously some revisions were made, at this point it seems that a new round of review is required to reevaluate the contribution and ensure that it is properly appreciated.
Decision: Reject